Assignment 1: Adventures in algorithms, and other digital diversions

CSC 106 Assignment 1: Adventures in
algorithms, and other digital diversions
Marks: 50 marks.
Learning Goals:
At the end of this assignment you will be able to:
• Create a brief biography of an historical computer scientist;
• Analyze a step by step activity and create a pseudo-code algorithm describing it;
• Analyze a step by step activity and create a flow-chart describing it;
• Move between binary (base 2), decimal (base 10), hexadecimal (base 16), and 2’s
complements encodings ;
Submission: This assignment is to be done individually. The assignment should be
submitted in .pdf format and attached to the CSC106 Assignment 1 submission page on
conneX.
NOTE:
Please make sure that you include the Task number/section you are answering above your
response. This makes it easier for your marker to stay with the flow of your answers.
Resources:
• Example of an introduction: Check out the introduction given by Professor Mary
Sanseverino for Dr. Kelly Gotlieb when UVic conferred an honorary degree on
him in the November 2011 convocation. It is attached to Assignment 1 in conneX.
This sample introduction is 600 words long - yours must be 200 word max.
• A basic introduction to flowcharts (don't worry about the actual computer code,
concentrate on the flowchart as a graphic representation of an algorithm:
http://www.eod.gvsu.edu/~blaucha/c2d2/Structured%20Design%20Using%20Flo
wcharts.pdf
• A basic description of several techniques for checking the "primality" of an
integer can be found here: http://www.wikihow.com/Check-if-a-Number-Is-Prime
• Some practice with Binary, Hexadecimal, and 2’s Complement conversions.
http://voyager.egglescliffe.org.uk/mwc/mukoku/mod/resource/view.php?id=514
TASK 1: Create a brief introduction to an historic
Computer Scientist (15 marks)
You are tasked with introducing an historical computer scientist to an audience of about
150 people. In general, the audience members are well educated and informed. However,
they ARE NOT computer scientists.
In your own words write a brief introduction - no more than 200 words - designed to
"bring the audience up to speed" on some of the accomplishments of this historical
computer scientist. Your introduction should give the audience some sense of why these
accomplishments are important and/or what they mean in the bigger picture of computer
science and technology.
You may select your historical computer scientist from the following list:
Charles Babbage;
Ada Lovelace;
Alan Turning;
John von Neumann;
Grace Hopper;
Donald Knuth;
Edsger Dijkstra
List and cite the reference materials you used for the introduction directly below the
introduction itself. You may use any citation style you like (e.g. MLA, APA, etc.).
A note: Don’t just copy the Wikipedia entry – we know what it says for each of these
folks and will give a 0 for this component if plagiarism is detected. Of course, Wikipedia
could be a good place to start your research – just don’t let it be what you turn in!
TASK 1 DELIVERABLES: A word processed document containing the Task heading,
the introduction (written in your own word), and references/citations listed below the
introduction. Marks will be assigned as follows:
5 marks - accuracy of content
5 marks - relating accomplishments to the bigger computer science picture.
5 marks - grammar, spelling, and communication skills
TASK 2: Analyzing an algorithm. (5 marks)
In the most general sense an algorithm is a set of step-by-step instructions designed to
solve a problem. As you will have seen from readings and lectures in the first two weeks
of this course, sometimes recipes are used as a metaphor for algorithms. Consider the
recipe below:
Mary's Tasty French Toast
• Combine 2 slightly beaten eggs with 1 tsp vanilla extract, ½ tsp cinnamon, 1 cup
milk
• Dip 6 slices of bread in mixture
• Fry in small amount of butter until golden brown
• Serve bread with maple syrup, sugar, or oregon grape jelly
While most of us could probably follow this recipe and create a tasty breakfast, this
recipe fails as an algorithm.
List five ways this recipe fails as an algorithm and describe why these are problems. It
helps if you imagine a programmable robot using this recipe to make French Toast.
TASK 2 DELIVERABLES:
Using the same word processed document as you created for Task 1 make a new Task 2
heading. Put a copy of the recipe under the Task 2 heading and give your answer. Marks
will be assigned as follows:
2 marks for correctly identifying five problems.
3 marks for well reasoned problem descriptions.
TASK 3: Algorithm creation - flow charting and
pseudo-code. (20 marks)
Try your hand at creating an algorithm designed to determine if a given string
is a palindrome. A palindrome is a word that is the same spelled backwards
and forwards. ie. anna OR madam
TASK 3 DELIVERABLES: Using the same word processed document as you created
for Task 1 make a new Task 3 heading. Below this heading, create a flow chart that
describes your algorithm to test a string to see if it is a palindrome. Use flow chart
symbols as discussed in class for your diagram. Include a key to the flow chart symbols.
Below your diagram please write out your algorithm in English-based pseudo code.
5 marks for correct logic and good structure.
5 marks for correct flow of control through the program.
5 marks for readability of pseudo code.
5 marks for correct flow chart diagram.
TASK 4: Some binary and hex fun . (10 marks)
1) (3 Marks) In our research of historical figures in lecture we discussed Alan
Turning. If you recall, Alan died at a very young age of 41. Lets make a cake
for Alan’s last birthday! It seems appropriate that we represent his age in
binary. Draw your answer on a cake. You can use the graphic below if you
like or, you can create one yourself.
2). (2 marks) What about hexadecimal?!!? What would Alan’s age at his last
birthday be in hexadecimal?
3). (3 marks) You are given two hexadecimal quantities. You are asked to state
their corresponding values in decimal. Since you are competent, you know that
the values depend on the context, so you have to pay attention to the column
headings in the table below. Moreover write in the first column the
corresponding binary quantity
Happy Birthday Alan
Hex Binary value in
8 bits
Integer -
unsigned
Integer – signed
magnitude
Integer - 2’s
compliment
D316
3D16
4). (2 marks) Convert the following to Binary (2’s complement) using 8 bits
Signed decimal Convert to Binary (2’s complement) using 8 bits
-32
14
-154
43
TASK 4 DELIVERABLES: Using the same word processed document as you created
for Task 1 make a new Task 4 heading. and put your completed diagram and filled-in
tables below it. With the diagram, describe any assumptions that are represented in your
diagram.
3 marks for correctly representing Alan’s age in candles using base 2.
2 marks for correctly answering the base 16 question.
3 marks for Task 4, question 3 (please use the table)
2 marks for Task 4, question 4 (please use the table).
Final note -- the staff at the Computer Science Assistance Center on the 2nd floor of
ECS are there to help you. They can't "do" the assignment for you, but they can help out
with application problems, printer problems, understanding questions, saving documents,
uploading and moving files, etc. They should be especially good with the
binary/decimal/hex questions. Call on them for help.