CISC 320 Introduction to Algorithms

Taught by Andy Novocin

Class times: TR 3:30-4:45 located at 209 Smith Hall

Office hours: T 1:30-3:00 W 2:00-4:00 R 9:45-10:45 location Smith 430

Teaching Assistant: Haozhu "Peter" Wang

TA Email: haozwang@udel.edu

Homework help hours: M 10-12 located at 201 Smith Hall

Text: Skiena, The Algorithm Design Manual, 2nd Edition, Springer, 2010

References:
Basse and Van Gelder, Computer Algorithms , Addison Wesley, 2000.
Cormen, Leiserson and Rivest, Introduction to Algorithms, McGraw-Hill & MIT Press, 1990.
Dasgupta, Papadimitriou, and Vazirani, Algorithms, McGraw-Hill, 2008.
Goodrich and Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley, 2002.
Kleinberg and Tardos, Algorithm Design, Addison Wesley, 2006
Sedgewick, Algorithms in C++, Addison Wesley, 1992.

After mastering this material you should be able to appropriately address a wide range of algorithmic problems, both in theory and in practice.

Along the way you should:

• Understand and appreciate asymptotic complexity analysis. Practically this allows thinking at the correct granularity when facing a problem.
• Master an arsenal of effective and efficient algorithmic techniques. This includes knowing when a technique is applicable and how you might effectively apply it.
• Understand and appreciate the large class of difficult problems which have no known efficient solutions. Here you want to know when it is appropriate to reduce your expectations of success, how to proceed when your problem is a difficult one, and how you might prove its difficulty to others.
• Demonstrate knowledge of canonical algorithmic domains. This allows you to communicate your approach effectively, understand a large range of problems, and transform problems of a unique nature into ones which are well studied.
• Apply your analysis to real problems with real implementations using C/C++.

Canonical domains: Models of computation, big-Oh notation, various data structures, graphs and classical graph problems, sorting ad nauseum, P vs NP, basic matrix algorithms, basic polynomial arithmetic, big integers

Assignments and tests provide measurable feedback mechanisms. If done correctly they will force you to internalize the material and prove to the world that you have some basic level of mastery. Grades can only provide a lower bound on your talents, the rest is up to you.

This material is best learned by beating your head against it, hashing out ideas both good and bad, and debating the merits of different approaches. YOU WILL BE PARTNERING WITH ANOTHER STUDENT TO ASSIST THIS VALUABLE PROCESS.

There will be six homework assignments (HW1-HW6) (at cs.prof.ninja/hw) which you will complete with your partner, turning in a single assignment per group. Please indicate the writer, and alternate throughout the semester. If you cannot find a partner I will assign them randomly. If you are having problems with your partner then I will reassign you and give you a dirty look. You will be allowed one free late assignment without questions asked, use it wisely.

There will be four programming assignments (PA1-PA4) (at cs.prof.ninja/programs). These will be done as a team of four (two sets of partners). For these assignments you will need to have working C/C++ code which you present to me. On the presentation day I will pick one of the four at random to explain your work to me. The programming assignments will always be evaluated on a Wednesday with groups being scheduled 45 minutes apart throughout the day.

There will be two mid-term tests (T1, T2) and a final exam. The vast majority of the problems will be pulled directly from the Skiena text.

There will be daily problems (at cs.prof.ninja/daily) due within the first 10 minutes of every class beginning on August 28th. These will only be checked for your name and some attempt but not graded.

Follow along with my slides at cs.prof.ninja/slides

There will be sporadic extra credit opportunities which will not amount to very much in the final grade.

• First daily problem due on 8/28 and every class after
• HW1 due 9/11
• PA1 presented 9/17
• HW2 due 9/25
• T1 test on 9/30
• PA2 presented 10/8
• HW3 due 10/16
• PA3 presented 10/29
• HW4 due 10/30
• No class 11/4 Elections
• T2 test on 11/6
• HW5 due 11/20 11/25
• No class 11/27 Thanksgiving
• HW6 due 12/2 Cancelled
• PA4 presented 12/3
• Final Exam : December 12 3:30-5:30 Smith 209

• Tests: 70% (roughly 20% 20% 30%)
• Daily problems: 6%
• Homework problems: 12%
• Programming Assignments: 12%

Extra Credit will involve programming challenges and can add no more than 3% to your final grade.

We live in the internet age, I understand that you can probably find ways of solving every problem that I ask of you without any true effort. I ask two things:

1. Please recognize that the purpose of assignments is to encourage you to struggle with the work. Without that struggle you sabotage your own understanding, your future in computing, and likely your test scores.
2. If you do use someone else's ideas or words please cite your source. You will still get credit for synthesis of a solution, but not as much credit or benefit as attempting your own solution.