CS2420 | Introduction to Algorithms and Data Structures | Fall 2016

PROFESSOR: Dr. Miriah Meyer
LAB INSTRUCTOR: Ryan Sargent

LECTURES: M/W 3-4:20pm
PLACE: L104 WEB

LABS: F various times
PLACE: 3225 MEB

OFFICE HRS: T 2-4pm, WEB 4887

This course provides an introduction to tools found throughout computer science -- basic algorithms and data structures that lend themselves naturally to computational problem solving, and engineering computational efficiency into programs. Students will gain an understanding of classical algorithms (including sorting, searching, tree and graph traversal) and data structures (including linked-lists, trees, graphs, hash tables, and heaps). Students will complete extensive programming assignments that require the implementation and testing of these concepts.

schedule

week date topic homework exams
1 8/22 & 8/24 Introduction & Java review 01 | Matrices | solo
2 8/29 & 8/31 OO & generics 02 | Generic Books | solo
3 9/7 Algorithm analysis 03 | Searching a List | pair
4 9/12 & 9/14 Basic sorting 04 | Anagrams | pair
5 9/19 & 9/21 Recursive sorting 05 | Quicksort and Mergesort | pair
6 9/26 & 9/28 Linked lists & midterm review 06 | Linked Lists | solo
7 10/3 & 10/5 Stacks & queues 07 | Symbol Matching | solo Midterm 1 on Monday
fall break
8 10/17 & 10/19 Trees 08 | Binary Search Trees | pair
9 10/24 & 10/26 Graphs 09 | PacMan! Graph Search | pair
10 10/31 & 11/2 Hash tables 10 | Hash Tables | solo
11 11/7 & 11/9 Binary heaps 11 | Binary Heaps | solo Midterm 2 on Monday
12 11/14 & 11/16 Huffman compression 12 | Huffman Compression | solo
13 11/21 & 11/23 Assignment 13 details 13 | Filght Optimizer | pair
14 11/28 & 11/30 Data Visualization
15 12/5 & 12/7 Final exam review Final on Dec 12th at 3:30pm

ta's

Jordan Davis Kenzie Elliott Karla Kraiss Jake Pitkin

syllabus

prerequisites

Students are expected to have a working knowledge of Java and to be able to complete the tasks required in CS1410.

objectives The following are the expected outcomes for students completing this course:
  • Students will learn algorithms for basic searching and sorting, as well as the asymptotic behavior of each.
  • Students will become proficient implementing and using basic data structures fundamental to computer science including arrays, linked lists, stacks, queues, graphs, trees, binary search trees, Huffman trees, hash tables, binary heaps, and priority queues. Students will reason about the asymptotic behavior of basic operations on these data structures.
  • Students will regularly evaluate their solutions for efficiency through written reports. Evaluations will summarize efficiency in time (Big-O and/or actual running time), efficiency in space (memory requirements), and/or programmer efficiency (ease of implementation and maintenance) of solutions.
  • Students will improve on the object-oriented programming skills learned in CS 1410. Student understanding of the concepts of inheritance, polymorphism, and generic programming will be strengthened significantly by creating solutions with multiple levels of inheritance and by implementing generic versions of data structures.
  • Students will gain experience using and implementing recursion. Students will also be introduced to dynamic programming. Students will learn when to apply iteration or dynamic programming instead of recursion.
  • Students will methodically test their solutions according to a variety of testing models including white-box testing, black-box testing, and unit tests.
  • Students will gain experience designing, implementing, and testing solutions in pairs using the techniques of pair programming.
textbook

Data Structures & Problem Solving Using Java, 4th Edition. Mark Allen Weiss, Addison Wesley.

clickers

We will use Turning Technologies "clickers" for in-class participation. Lectures will contain questions which you will answer with your clicker. Clicker participation will count towards your grade.

You will need to register your clicker on the Canvas Modules page. You can also read instructions for purchasing a license and registering your account, or watch it in movie form.

online resources

Download: Java SDK 8
Download: Eclipse IDE for Java developers
Java API documentation
Java notes

Introduction to Programming Using Java
Brewing Java: A Tutorial
Sams Teach Yourself Java in 24 Hours
The official Java tutorials

C++ and Java Syntax Differences Cheat Sheet
A crash course from C++ to Java
A comparison of Java, C++, and Python

grading

Grades in this course will be determined by:

  • 50% assignments
  • 25% midterm exams (2)
  • 15% final exam
  • 10% participation and labs

Assignments consist of weekly programming assignments, some of which will be done in pairs. The specifications of these assignments will be posted online each week. The assignments will be due one week after they are released, with a one day late penalty of 10% -- assignments handed in more than one day late will not be graded. You will hand in your programs through Canvas. Partial credit may be given for incorrect programs, but it must be clear that a strong attempt was made. If your program does not compile or run, no credit will be given. Programs will be graded on readability, comments, and design of the code, as well as correctness in execution. Assignments will also consist of a written portion describing the design of the program, and documenting the performance of your code. All reports must be typed -- no scanned handwritten work will be accepted! You may request a regrade of your assignment within one week of receiving grades by contacting the TA that graded your assignment through the Canvas email system (no comments please).

The last assignment of the semester will be a comprehensive project lasting two weeks, in which you will design a solution to a problem from the ground up, with little or no framework given to you. You will have the freedom of selecting which algorithms and data structures are best suited to solving the problem, and designing a complete program around your solution.

Midterm exams will be given during the regular class time in the regular class room. The final exam will take place on Monday, December 12th from 3:30-5:30pm in the regular class room. All exams are written exams. As an anti-cheating measure, students who fail the exams will fail the class regardless of their assignment scores.

The class participation grade will be based on completion of lab exercises, clicker responses, and overall contribution to the class and labs.

The final grade will be calculated from exams, programming assignments, written homework, and laboratory exercises. A's will be given to students within 90%, B's within 80%, C's within 70% etc. I do, however, reserve the right to adjust this loose scale if need be.

getting help

Every student will get stuck sooner or later. When you do, feel free to ask for help in person or through the class website. We are happy to help.

In-person help is the most effective way to learn. Please make use of our office hours whenever possible. TAs will hold their office hours in the CADE lab, WEB L224 and WEB L226. When you arrive for TA hours, use the TA call queue to request TA help.

The student-to-student Canvas forum is where you should post simple questions for other students. If you'd like to find a study partner, if you discover something really cool, or if you just have a simple question, feel free to post to this forum. The only rule is that you are not allowed to discuss specific solutions to upcoming homework.

For help from the teaching staff, use teach-cs2420@list.eng.utah.edu. Emails to this address will be sent to all of the teaching staff and you can expect to receive a response within 24 hours.

For emails directed to me personally, I will read it quickly and respond as soon as possible, but I get thousands of emails each semester and you may not get a response. For time sensitive issues or issues that require a little more privacy, please talk to me immediately after class or come to my office hours.

TA call queue
student-to-student Canvas forum
teach-cs2420@list.eng.utah.edu

pair programming

About half of the assignments will be completed in pairs -- each assignment specification will clearly state when work must be done individually or in pairs. When pair-work is required, students must adhere to the techniques of pair programming. Partners are required to contribute equally half of the work and problem solving required for each assignment. Students are encouraged to discuss high-level solution strategies with fellow classmates, but each student is responsible for writing her/his own answer.

Note that the teaching staff will not answer questions on pair programming assignments unless both partners are present.

cheating policy

Cheating is: sharing (outside of a partnership) written or electronic work either by copying, retyping, looking at, or supplying a copy. And by copy, we mean a copy that belongs to someone else, or your own copy from a previous instantiation of this course. Cheating is not: discussing concepts, answering questions about concepts or clarifying ambiguities, or helping someone understand how to use the class tools and software. There must be no collaboration during tests or the final exam. There is a detailed policy that defines cheating for this course. Any student found cheating will fail the course. Supplying cheated materials is considered cheating just as using them is.

School of Computing Policy Statement on Academic Misconduct

lectures : labs : assignments

W1. INTRODUCTION & JAVA REVIEW | AUG 22 & 25

reading - Data Structures & Problem Solving Using Java, Chapters 1 and 2.
lab - Lab 1: Testing
homework - Proficiency exam
- Assignment 1: Matrices, due Wednesday, Aug 31st at 11:59pm
slides - L01-intro.pdf
- L02-java-review.pdf

W2. OO & GENERIC PROGRAMMING | AUG 29 & 31

reading - Data Structures & Problem Solving Using Java, Chapters 3 and 4.
lab - Lab 2: debugging
homework - Assignment 2: Generic books, due Wednesday, Sept 7th at 11:59pm
slides - L03-oop.pdf
- L04-generics.pdf

W3. ALGORITHM ANALYSIS | SEPT 7

reading - Data Structures & Problem Solving Using Java, Chapters 5 and 6.
lab - Lab 3: timing
homework - Assignment 3: Searching a List, due Wednesday, Sept 14th at 11:59pm
slides - L05-complexity.pdf

W4. BASIC SORTING | SEPT 12 & 14

reading - Data Structures & Problem Solving Using Java, Chapter 8.1 - 8.4.
lab - Lab 4: debugging
homework - Assignment 4: Anagrams, due Wednesday, Sept 21st at 11:59pm
slides - L06-sorting.pdf
- L07-sorting-part2.pdf

W5. RECURSIVE SORTING | SEPT 19 & 21

reading - Data Structures & Problem Solving Using Java, Chapters 7, 8.5 - 8.8.
lab - Lab 5: random number generators
homework - Assignment 5: Quicksort & Merge sort, due Wednesday, Sept 18th at 11:59pm
slides - L08-recursion.pdf
- L09-merge-quick-sort.pdf

W6. LINKED LISTS & MIDTERM REVIEW | SEPT 26 & 28

reading - Data Structures & Problem Solving Using Java, Chapter 17.
- Open Data Structures (in Java), Chapter 3.
lab - Lab 6: midterm review
homework - Assignment 6: linked lists, due Wednesday, Oct 5th at 11:59pm
slides - L10-linked-lists.pdf
- L11-midterm1-review.pdf

W7. STACKS & QUEUES | OCT 3 & 5

reading - Data Structures & Problem Solving Using Java, Chapter 16.
- Open Data Structures (in Java), Chapter 2.
lab - Lab 7: iterators and eclipse movement
midterm 1 - Monday, in class
homework - Assignment 7: Symbol Matching, due Wednesday, Oct 19th at 11:59pm
slides - L12-stacks.pdf

W8. TREES | OCT 17 & 19

reading - Data Structures & Problem Solving Using Java, Chapters 18 and 19.
- Open Data Structures (in Java), Chapter 6.
lab - Lab 8: BST
homework - Assignment 8: Binary Search Trees, due Wednesday, Oct 26th at 11:59pm
slides - L13-trees.pdf
- L14-bst.pdf
demo code - L13.zip

W9. GRAPHS | OCT 24 & 26

reading Data Structures & Problem Solving Using Java, Chapter 14: Graphs.
lab - Lab 9: Pacman and intro to Java from the command line
homework - Assignment 9: PacMan!, due Wednesday, Nov 2nd at 11:59pm
slides - L15-graphs.pdf
- L16-graphs2.pdf

W10. HASH TABLES | OCT 31 & NOV 2

reading - Data Structures & Problem Solving Using Java, Chapter 20.
- Open Data Structures (in Java), Chapter 5.
lab
- Lab 10: Java -- Arguments and the Class Path
homework - Assignment 10: Hash Tables, due Wednesday, November 9th at 11:59pm
slides - L17-graphs3.pdf
- L18-hash-tables.pdf

W11. BINARY HEAPS | NOV 7 & 9

reading - Data Structures & Problem Solving Using Java, Chapter 21: Binary Heaps.
midterm 2 - Monday, in class
lab - Lab 11: File Finding from the Command Line
homework - Assignment 11: Binary Heaps, due Wednesday, Nov 16th at 11:59pm
slides - L19-binary-heap.pdf

W12. HUFFMAN COMPRESSION | NOV 14 & 16

reading - Data Structures & Problem Solving Using Java, Chapter 12.
lab - Lab 12: Obstacle Course
homework - Assignment 12: Huffman Compression, due Wendesday, Nov 23rd at 11:59pm
slides - L20-binary-heaps2.pdf
- L21-huffman.pdf
tutorial - min-max heap tutorial

W13. DIJKSTRA'S | NOV 21

homework - Assignment 13: Flight Optimizer, due Wednesday, Dec 7th at 11:59pm
slides - L22-dijkstra.pdf

W14. DATA VISUALIZATION | NOV 28 & 30

reading - A Tour through the Visualization Zoo. Jeffrey Heer, Michael Bostock, Vadim Ogievetsky. Communications of the ACM, 53(6), pp. 59-67, Jun 2010.
homework - Assignment 13: Flight Optimizer, due Wednesday, Dec 7th at 11:59pm
lab - Lab 13: The End
slides - L23-visualization.pdf

W15. FINAL EXAM REVIEW | DEC 5 & 7

final - Monday, December 12th at 3:30pm
slides - L24-review.pdf