CS 100 Principles of Computing Schedule Fall 2024 HW1 Bits and Algorithms Due Monday September 9th Submit on CANVAS by the Deadline TABLE OF CONTENT 1 GENERAL INSTRUCTIONS 1 2 GRADING RUBRIC 2 3 PROBLEM 1 BABYLONIAN ALGORITHM 2 4 PROBLEM 2 BITS FOR NUMBERS CONVERTING BETWEEN BASES 2 5 PROBLEM 3 BITS FOR NUMBERS CONVERTING BETWEEN BASES 3 6 PROBLEM 4 COMBINED GREEK LATIN AND TURKISH ALPHABET 3 7 PROBLEM 5 DIGITAL CLOCK 4 1 GENERAL INSTRUCTIONS students Complete the problems in each section below which is labelled Problem This is an individual assignment you must do your own work and may not share or compare answers with other Document your work using in an acceptable electronic format Acceptable formats are limited to 1 A Microsoft Word Document doc or docx extensions 2 A PDF portable document format pdf 3 Plain text txt You may work in other programs Apple Words Google Docs etc but make sure you can export save as your work to an acceptable format e g PDF before submitting it Submit your document on CANVAS o Log in to CANVAS o Select Modules from the left navigation bar o Locate Week 2 Module 2 Bits and Logic module o Click to Select the module item titled 2 4 Homework HW 1 Bits ad Algorithms under the B Activities o Scroll down to locate the Upload button o Click on the Upload button to browse and upload your file Submitting the wrong file will result in a 0 so check to ensure you submitted the correct file before signing off o Click on the green Submit Assignment button located on the right bottom corner of the page to submit section the assignment file 1 2 GRADING RUBRIC Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Criteria Answer is Correct 5 points Demonstrated understanding of Question 2 Points or Showed 3 Iterations of the Algorithm 3 Points 1 Point for Each Correct Answer 6 parts 6 Points Showed Work 4 Points 1 Point for Each Correct Answer 5 parts 5 Points Showed Work 5 Points Answer is Correct 5 Points Explanation Given for Answer 5 Points 2 Points for Each Correct Representation 3 parts 6 Points Showed Work 4 Points Points 10 10 10 10 10 Total 50 Points 3 PROBLEM 1 BABYLONIAN ALGORITHM Description Recall the Babylonian Algorithm for calculating a square root that we discussed in class It works as follows S is an input number the algorithm calculates square root of S Repeat Initialize Set x to a guess o Calculate o o 1 2 If the result is close enough if x2 is close to S then quit Requirements Demonstrate 3 Iterations of the Babylonian Algorithm Use the Babylonian Algorithm to calculate an approximation for the square root of 17 which is 17 4 12310562562 Use an initial guess of 2 Perform the Repeat section 3 times Feel free to use a calculator to help with addition subtraction Show the results you compute at each step Include after each step the calculation how close 2 is to 7 which gives an indication of how close one is to the true answer Hint After one iteration the difference should be 2 0 5625 Documenting the Answer show your work by demonstrating the 3 iterations of the Babylonian algorithm You may do any of the following o Type your work directly in the Word document o Calculate using pen pencil and paper scan or take a photo of your work and inserted in the Word document o Follow the same option for the rest of the problems 4 PROBLEM 2 BITS FOR NUMBERS CONVERTING BETWEEN BASES Description Convert the numbers from base 2 Binary to base 10 Decimal and base 10 Binary to Base 2 Binary For full credit show your work for each number Requirements 2 1 Convert the following numbers from base 2 Binary to base 10 Decimal The subscripts small numbers at the end represent the bases they are not part of the number For example 10002 is just Binary number 1000 which is the Decimal number 8 when converted 2 Convert the following base 10 numbers to base 2 using 8 bits For full credit show your work for each number 101012 convert to base 10 1110112 convert to base 10 0011112 convert to base 10 Example 8 converted to base 2 is 00001000 1001010 convert to base 2 431010 convert to base 2 611010 convert to base 2 This tutorial gives you several ways of converting decimal numbers to binary I tend to favor the first method which involves repeatedly dividing by two and keeping track of remainders Documenting the Answer Your answers to the 3 binary numbers to decimal conversion problems above Your answers to the 3 decimal numbers to binary conversion problems above Don t simply put down the answer Show your work to receive full credit 5 PROBLEM 3 BITS FOR NUMBERS CONVERTING BETWEEN BASES Description Write representations of decimal numbers in binary and state whether it is possible to represents the number or not Requirements Write representations for the following If it is not possible to do the representation put Impossible Represent 11010 with 7 bits Represent 200010 with 10 bits Represent 610 with 3 bits Represent 1210 with 4 bits Represent 3000010 with 16 bits Documenting Answer Your answers to the above 5 representation problems Show your work to receive full credit 6 PROBLEM 4 COMBINED GREEK LATIN AND TURKISH ALPHABET Description In general Bits are often used to represent letters in some alphabet termed a character code The most common character code is the ASCII code which is focused mainly on English speakers Here we will determine the number of bits required to represent some other alphabets of languages around the world As a starting example consider the Latin English character set which is A to Z 26 upper case characters and a z 26 lower case characters How many bits would be required just to represent these characters A sequence of N bits can represent up to 2N distinct objects So we can count up 3 With 1 bit we can represent 21 2 objects With 2 bits we can represent 22 4 objects With 3 bits we can represent 23 8 objects With 4 bits we can represent 24 16 objects With 5 bits we can represent 25 32 objects With 6 bits we can represent 26 64 objects There are 26 lower case plus 26 upper case characters in the Latin English character set for a total of 52 objects With 5 bits we could get lower or upper case but to represent both we ll need to use 6 bits which can represent up to 64 different objects The Greek alphabet has 24 lower case characters and 24 upper case characters The Turkish alphabet has 29 characters Requirements Suppose we want a character encoding which can represent both English Greek and Turkish characters in a mixture What is the minimum number of bits