CS 105 Introduction to Data Structures and Algorithms
(Theory of Algorithms)
2nd Semester, 2014-2015

Instructor:
John Paul Vergara (Section B)

Announcements

• Your major project for the semester has been posted. See Projects section.
• There will be no classes on Friday, December 19. Have a Merry Christmas!
• Take note of the HW due when you return from the Christmas break; I suggest that you work on it before the break :)
• Welcome to this website! Visit this link regularly for section-related course material, announcements and updates

Projects/Labs/Seatwork/Homework

• November 17:
  1. Create a Console application in C#. In the Main() method, insert the following code

                 int x;
                 x = 2147483646;
                 Console.Out.WriteLine(x);
                 x++;
                 Console.Out.WriteLine(x);
                 x++;
                 Console.Out.WriteLine(x);
                 Console.ReadLine();
     

     Compile and execute. Take note of the output produced and be prepared to explain why the output is such. No submission required.
  2. Write binary-to-decimal and/or decimal-to-binary programs in C#. You may choose to write only 1 conversion program, but you may do both. I have started you off with the C# projects and you can find them here; all you need to do is complete the C# function. For reference, here are working executables that carry out the conversion. When done, submit a zip file containing the project(s) via Moodle.
• HW due January 5, 2014 2015 :-)
  1. Download this C# project . The program demonstrates polynomial evaluation. Note that the input file required by the program is stored in the bin\Debug folder.
  2. The method EvalPoly1() is an O(n^2) algorithm that evaluates a polynomial P on a value a. Fill in the code for EvalPoly2() to come up with a better (linear-time) polynomial evaluation algorithm.
  3. Provide the running times for EvalPoly1() and EvalPoly2() (your algorithm). Your answers must be in terms of n (where n is the degree of the polynomial). You should count assignments, additions, multiplications, comparisons, array accesses, and return statements. Note that an increment counts as two operations: an addition and an assignment. Subtractions and decrements (if applicable) count as additions or increments. Place your answers in a HW1.doc or HW1.txt file. Show your solutions.
  4. Submit a zipped file containing ONLY the revised Program.cs file of your C# project, the text or word document containing your time complexity analysis, and your certificate of authorship. You may work in pairs. The name of the zip file should contain the names of the members, e.g., HW1-Lastname1-Lastname2.zip. Submit via moodle.
  You will be graded according to how well your algorithm compares against the current algorithm. Take note of the output files produced.
  Tips:
  1. After executing, go to the bin\Debug folder, and from a command line, type the following command: fc output1.txt output2.txt to check if your PolyEval2() method is correct.
  2. Research on Horner's rule . It provides an efficient linear-time polynomial evaluation algorithm.
• January 23 Lab:
  1. Download this C# project that demonstrates the O(n^2) algorithms discussed in class.
  2. Compile and execute and notice that three algorithms are implemented
     1. Insertion Sort
     2. Selection Sort (the version that repeatedly selects the minimum element)
     3. Bubble Sort (the version that repeatedly positions the maximum element)
  3. Fill out the unimplemented versions of Selection and Bubble Sort; i.e.,
     1. Selection Sort that repeatedly selects the maximum element
     2. Bubble Sort that repeatedly positions the minimum element
  4. When done, zip the revised project, rename the zip file Lab-Sort-Lastname.zip, and submit via moodle . You are to submit individually.
• Lab due Feb 23 1030am: Implement either a Dictionary or PriorityQueue. Go to moodle for template code and submission link.
• Project due on March 20: Specs
  Sample cellphone number list
  Sample data
  • sample transactions 1 => corresponding output
  • sample transactions 2 => corresponding output

Slides and Other Course Material

• Slide sets common to all sections are posted via moodle
• Demo of Sorting Algorithms (C# projects)
  • Insertion, Selection, and Bubble Sort ==> Program.cs
  • Quick Sort ==> Program.cs
  • Bucket Sort ==> Program.cs
  • Radix Sort ==> Program.cs (updated!)
• Queue demo in C#: CSharp Project ==> Program.cs
  Dictionary demo in C#: CSharp Project ==> Form1.cs , executable
  Stack demo in C# (ArrayStack Implementation): CSharp Project ==> Program.cs
  

Links

• Moodle
• Paul Echevarria's Sorting applet