Description

CS420 is about learning and practicing principles for organizing your thinking when solving programming problems, and not about memorizing details and facts. You must practice ways of establishing that an algorithm is correct and analyzing its time bound. Getting good at these skills will allow you to come up with efficient algorithms of your own, by figuring out what steps are needed in the pseudocode or program code to get the proof of correctness to go through, or to reduce the running time. You will also learn to recognize what kinds of optimizations on a program are a waste of time, as they will have little or no impact on the running time of the program as a whole.

The following are techniques for algorithm design that we will study in the class:

  • Advanced big-O analysis
  • Reduction of one problem to another
  • Advanced implementation and use of abstract data types
  • Use of mathematical induction in designing algorithms
  • Analysis and design of parallel algorithms
  • Amortized analysis
  • Randomized algorithms
  • Advanced examples of applications of techniques from a first-semester algorithms class: greedy strategies and proofs, dynamic programming, divide-and-conquer strategies
  • NP-completeness

Some of these techniques are covered in CS320; we will cover them at a more advanced level. The following are some illustrations of these topics that we may study, time permitting, together with the techniques they illustrate:

  • Strassen's algorithm -- divide-and-conquer strategy
  • Sorting networks -- divide-and-conquer; parallel algorithms
  • Fast Fourier Transform -- divide-and-conquer; parallel algorithms and architectures
  • Currency arbitraging -- reduction as an algorithm-design technique
  • Floyd-Warshall -- dynamic programming
  • Johnson's algorithm -- problem reduction as a design technique
  • Max flows, min cuts -- reduction as a design technique; use of invariants
  • Sorting, convex hull, Euclidean minimum spanning tree -- use of reduction to obtain lower bounds
  • SAT, 3-SAT, CLIQUE, VERTEX-COVER, SUBSET-SUM -- use of reduction to show NP-completeness and NP-hardness
  • VERTEX-COVER, EUCLIEAN-TRAVELING-SALESMAN, SUBSET-SUM: approximation algorithms for NP-hard problems
  • Maximum global separator in graphs -- randomized algorithms
  • MAX-3-SAT -- randomized algorithms; approximation algorithms
  • Median finding and Quicksort -- randomized algorithms
  • Hash tables -- randomized algorithms; amortized analysis
  • Splay trees -- amortized analysis; designing new ADT's

Personnel

Sections 001, 301
Instructor: Hamid Chitsaz
Email: chitsaz@colostate.edu
Office: CSB 342
Office Hours: MW 3:00 pm - 4:00 pm
Lecture: 2:00 pm - 2:50 pm, MWF, Wagar 133
GTA
Dave Besen
Email: David.Besen@colostate.edu
Office: CSB 120
Office Hours: 2:00 pm - 4:00 pm Thursday
UTA
Ethan Coldren
Email: ethancorvids@gmail.com
Office: CSB 452
Office Hours: 4:00 pm - 5:00 pm Thursday

Prerequisites

The following courses at CSU, or the equivalent courses at another school, with grade of C or better: CS320 (Algorithms) CS200 (Algorithms and Data Structures); MATH160 and MATH161 (two semesters of calculus); MATH 229 or 369 (linear algebra and matrix operations); CS160 and CS161 (object-oriented programming and discrete math).

Textbook

  • Introduction to Algorithms, Third Edition. Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein. MIT Press, 2009.
  • Algorithm Design, First Edition. Jon Kleinberg and √Čva Tardos. Addison Wesley, 2005.

Recitation Time and Place

4 pm - 4:50 pm, Wednesday, CSB 130 (Ethan, Dave)

Grading

Here are the formally graded elements of the course and associated weighting:

Activity Weight
Final Exam 30 %
Midterm 30 %
Assignments 25 %
Quizzes 15 %

You are expected to do the readings before the corresponding class and come to class with questions that you've gotten stuck on. Bring your textbook to each class. Learning how to read texts and other literature of our field fluently is one of the skills that we want you to develop in the course. It takes practice, but once you get good at it, it's surprisingly easy. During each lecture, ask questions. An important step is then to re-read the corresponding reading and figure out, with the benefit of hindsight, how you could have gotten un-stuck without the help of the lecture.

Another reason you are expected to do the readings before class is that classroom time is a scarce resource that must be shared with your classmates. We don't want to waste some of it repeating trivial issues that everybody is capable of understanding by looking in the text.

Revisit the same material many times over many days, refining and simplifying your understanding of it each time, asking yourself questions about it. The class will take significantly fewer hours out of your week, it will be more interesting, and you will get more out of it if you approach it in this way. way.

I will sometimes give a homework quiz on the homework on the due date. (This is to ensure that people are making responsible use of the permission to talk with other students about the homeworks.) I will also give unannounced quizzes on the readings to make sure you are practicing the reading techniques we will talk about in the course.

Each homework assignment will consist of written work and/or programs. See below for my policy regarding late homeworks.

Plagiarism in coding: This is a difficult issue. It is impossible to prevent "borrowing" code from web sources, especially for well established algorithms and data structures. In most cases, we have structured the programming assignments such that any borrowed code will need to be modified. If you have started your program using code from another source, you need to make that clear in your comments.

Sources that are acceptable are: the textbook and reliable Web repositories. Sources that are not acceptable: other students in the class, friends who have taken CS420 before, tutors, paid programmers found on programmer for hire web sites...

When code has been taken from an acceptable source and modified, a comment must be added that explains the provenance (origin and creator) of the code. It is only fair to give credit where it is due. Failure to do so may result in a charge of academic dishonesty.

Quizzes are given during the lecture class; no quizzes will be given in those weeks in which a midterm exam is being given. No makeups will be given for quizzes, but the lowest quiz grade will be dropped.

Exams will be given during the lecture class except for the final exam whose time is determined by the university.

Exams and assignments will be done individually and grades assigned on an individual basis. Further, students not already familiar with the CSU Honor Pledge should review this clear and simple pledge and always adhere to it.

Homework and exam grades are curved to give a distribution of grades that is consistent with those in other senior-level undergraduate classes at CSU. Each assignment, quiz, or exam is assigned a raw score, and then a curved score. Canvas will give you a running average of your grades. The assignment of letter grades will be made following one of the Canvas schemes.

Late and Makeup Policy

Midterm and Finals: Make-up exams are only given for extraordinary circumstances (e.g., illness, family emergency, won lots of money in the lottery). Students must consult with the instructor as soon as possible, preferably before the start of the exam. Course examination dates are listed in the syllabus; be aware of them and plan accordingly.

Projects: Unless otherwise specified, programming assignments are to be submitted electronically through Canvas. Specifics will be included in each assignment. Always check the assignment page for due dates. Late assignments submitted within 48 hours of the time required will receive a 10% late penalty. Electronic submission is closed 48 hours after assignments are due; students not having submitted programs receive an automatic zero on the assignment.

Important Dates

MidtermMonday, October 9 in class
Final Exam December 14 11:50am-1:50pm

Any written midterms and the final exam will be held in the same classroom as regular lectures. While no change to the midterm dates is anticipated, the instructor reserves the right to change these dates with a weeks notice.

Professional Conduct

All students are expected to conduct themselves professionally. We (the instructors and GTAs) assume you are familiar with the policies in the student information sheet for the department and the Conduct Code for the department. Additionally, you are computing professionals, albeit perhaps just starting. You should be familiar with the code of conduct for the primary professional society, ACM. You can read the ACM Code of Conduct HERE.

We work to maintain an environment supportive of learning in the classroom and laboratory. Towards that end, we require that you be courteous to and respectful of your fellow participants (i.e., classmates, instructors, GTAs and any tutors). In particular: