Assignments for Design and Analysis of Algorithms
- http://cs-netlab-01.lynchburg.edu/courses/central/GetStart.htm
- The Gamble Square Game Problem (Prog1)
- http://cs-netlab-01.lynchburg.edu/courses/Algorithms/SimProbs.htm
You must do the 0 to the 0 problem and one of the other three as Prog2.
- Page 37 do exercises 2.2-3 and 2.2-4,
Page 38 do problem 2-2. Upload your solutions to your erin account.
- Page 45 do exercises 3.1-1, 3.1-3, 3.1-7
Page 52 do exercises 3.2-1, 3.2-2, 3.2-4
- Anonymous ftp to cs-netlab-01.lynchburg.edu and download the file growth.doc from the Algorithms directory. The paper presents an alternative to teaching traditional big O notation to explain growth of functions. Review and be prepared to discuss this paper.
- Review Chapter 4 on Recurrence Relations and review the study guide.
- Write a recursive and an iterative program to compute N!. Run the program for increasingly larger values of N. Compare the results and comment.
Write a recursive and an iterative program to compute the Nth Fibonacci number. Run the program for increasingly larger values of N. Compare the results and comment.
These programs consititute Prog3.
TEST # 1
Review section 5.1, Sets, and complete problems 5.1-1, 5.1-4 and 5.1-5
Read section 5.4, Graphs, and become familiar with the terminology.
Do problems 5.4-1, 5.4-3, 5.4-4 and 5.4-6
Review section 5.5, Trees.
Do problems 5.5-4 and 5.5-5
On pages 97-98 do problems 5-1a, 5-1c, 5-2a and 5-2b.
Read Chapter 6 sections 6.1 and 6.2.
Do problems 1, 3, 4, 5, 6, 7, 9 and 10 on pages 104 - 105.
Do problems 2, 3, (others to be announced) on page 109.
Do the additional problems given here
Prog4 - Crypto encoder/decoder.
In this assignment you are to write a program that will encode and decode messages. The program must do the following:
- Allow the user to select whether he/she wants to encode or decode a message.
- Accept an input file name from the user. The input file will contain either an encoded message or plaintext to be decoded.
- Accept and output file name for the user.
- The program will read an encoded message file (if the user selected decode) decode it and write the plaintext to a file or (if the user selected encode) read a plaintext file and write an encoded message file.
For the purpose of this program you may embed the key in the program. Ordinarily this would not be the case. I.e., the key would be separate from the program and changeable by the user.
You may create your own encryption algorithm or you may use a variation of the one that I will give below. If you create your own it may not be trivial. The Caesar cypher and its simple variations are considered trivial in this day and age. A good encryption algorithm has the property that others may know the algorithm (i.e. even have the source code) and, thus, be able to generate as many plaintext/encrypted message pairs as they desire and still not be able to decode encrypted messages without the key. The Caesar cipher does not pass this test. A good algorithm is also immune to the most common attacks such as frequency analysis. Thus, nearly all algorithms that use byte permutations should be avoided. A better algorithm has the additional property that it will be secure even if the attacker possesses many plaintext/encrypted message pairs all encoded with the same (current) key. Finally, the best algorithms possess all of the aforementioned properties and do not require the exchange of the decryption key. Public key systems meet this test.
Here is a "reasonably good" encryption algorithm (we shall call it IGP) that is not too difficult to implement. Be aware that it does not even meet the better test given above so should not be used where secure communication is important.
Exercise:
Read the description of the IGP algorithm referred to above and see if you can determine how to "crack" it. You may assume that you have the source code to the program that encrypts and decrypts messages and that you have "many" plaintext/encrypted message pairs that use the currently active key. Two of the encrypted messages you have represent the same plaintext. You do not have the current key itself, obviously, but you have the ability to generate your own keys for testing purposes.
Hint: First determine how to recognize the inserted garbage bits. Second, determine how to reduce the number of possible bits that a particular bit (say bit 0) could permute to.
You may download a .EXE file that implements the above mentioned algorithm, together with a key file and a help file from cs-netlab-01.lynchburg.edu/courses/algorithms/crypto.
The .EXE will run on your computer only if you have the required Visual Basic support files loaded. You may download an installation/setup collection of files by anonymous FTP to cs-netlab-01.lynchburg.edu. Move to the Algorithms subdirectory and then to the Cryptog subdirectory under that. Download the file Cryptog.zip, unzip it and run setup.exe.
TEST # 2
Top of this page 
Home page 
