Announcements

• Old practice quizes (first second and third) are reposted.
• Additional review sessions are Monday May 3rd 7-9pm in the main lab and Tuesday 2:40-3:55.
• Final exam is May 6th 2-5pm in the main lab.

Introduction

This course completes the broad introduction to computer science begun in CS21. It provides a general background for further study in the field. Topics to be covered include object-oriented programming in C++, advanced data structures (such as priority queues, trees, hash tables, and graphs), advanced algorithms, as well as software design and verification. Students will be expected to complete weekly lab assignments illustrating the concepts presented.

Prerequisite: CPSC 21 or permission of the instructor. This course is designated as a Natural sciences and engineering practicum.

Goals for the course

• Understand the basic principles of object-oriented programming and learn how to create programs in C++ using this paradigm.
• Understand asymptotic growth and big-O notation.
• Analyze the performance of algorithms in terms of big-O notation.
• Given an algorithm, learn how to argue that it correctly solves the problem for which it was designed.
• Given a description of a data structure and its operations, write code to implement the data structure in C++.
• Understand the difference between an abstract interface and the implementation of that interface.
• Given multiple implementations of a data structure, analyze the performance of each implementation in terms of run-time and memory use and understand the tradeoffs of using one approach over another.
• Be able to combine multiple data structures in a coherent way to solve problems of moderate complexity.

Class information

Room: Science Center 240
Class: Tuesday, Thursday 2:40–3:55pm
Lab: Friday 2:00–3:30pm
Text: Data Structures and Algorithms in C++ by Goodrich, Tamassia and Mount

Instructional staff

Professor: Andrew Danner
Office: Science Center 253
Phone: 328-8665
Office hours: by appointment. Drop by if my door is open, or email me to set up a time

Student Support: Betsy Horner
Office: Science Center 255
Phone: 957-6062

Student Mentors (aka Ninjas): Kristen Allen, Ryan Carlson, Sarah Chasins, and Gregory Rawson

Schedule

WEEK	DAY	ANNOUNCEMENTS	TOPIC & READING	HOMEWORK
1	Jan 19		Introduction to C++ Ch1: pages 2-8, 10(strings), 16(using), 17-30	Lab1: Introduction to C++
	Jan 21
2	Jan 26		Object-Oriented Design in C++ Ch1: pages 33-38, 46-56; Ch2: pages 62-88	Lab2: Introduction to OOP
	Jan 28	Drop/Add ends (Jan 29)
3	Feb 02		Complexity Analysis Ch3: pages 108-134	Lab3: Analysis
	Feb 04	Quiz 1 (Feb 05)
4	Feb 09		Stacks and Queues Ch4: pages 156-182	Lab4: Maze solver
	Feb 11
5	Feb 16		Linked Lists Ch5: pages 217-226	Lab5: Skip List
	Feb 18
6	Feb 23		Sorting Ch10: pages 484-497, 504-521	Lab6: Generic Sorting
	Feb 25	Quiz 2 (Feb 26)
7	Mar 02		Trees Ch6: pages 254-280, 414-420
	Mar 04
	Mar 09	Spring Vacation
	Mar 11
8	Mar 16		Balanced Search Trees Ch9.3,9.4: pages 437-448 Paper	Lab7: Word Frequency
	Mar 18
9	Mar 23		Priority Queues Ch7: pages 312-324, 330-348	Lab8: Web Search
	Mar 25	Last day to declare CR/NC or withdraw with a "W" Quiz 3 (Mar 26)
10	Mar 30		Dictionaries	Lab9: Web Search Caching
	Apr 01
11	Apr 06		Graphical User Interface wxWidgets	Lab10: Browser GUI
	Apr 08
12	Apr 13		Graphs Ch12: pages 576-594	Lab11: Bacon Warmup
	Apr 15
13	Apr 20		More Graphs Ch12: pages 625-633	Lab12: Oracle of Bacon
	Apr 22
14	Apr 27		Make-up/Review
	Apr 29
	May 06	Final exams start
	May 15	Final exams end

Grading

Your overall grade in the course will be determined as follows:

40%	Lab assignments
30%	Quizzes
5%	Class Participation
25%	Final Exam

Lab assignment policy

Assignments will be introduced during lab on Fridays and will be due before midnight the following Wednesday night. You are strongly encouraged to start early and to attend the study sessions on Monday nights.

You will submit your assignments electronically using the handin35 program. You may submit your assignment multiple times, but each submission overwrites the previous one and only the final submission will be graded. Late assignments will not be accepted unless you contact me before the deadline. Even if you do not fully complete an assignment, you may submit what you have done to receive partial credit.

Study Sessions

Student mentors will assist me in class and run study sessions on Mondays 7—11pm in SCI 240 (where class meets).

You are invited -- and encouraged -- to participate in these study sessions to prepare for quizzes, to discuss programming concepts, and to get friendly assistance in working on lab assignments. As an added bonus, food will be provided.

Academic Accommodations

Academic accommodations are available for students with disabilities who are registered with Student Disability Services in the Dean's office. Students in need of disability accommodations should schedule an appointment with me early in the semester to discuss accommodations for this course that have been approved by the Dean's office. All requests must come through an accommodation letter from the Dean's office. To receive an accommodation for a course activity, your meeting with me must be at least one week prior to the activity.

Contact Tracey Rush at the Dean's office and follow these steps for obtaining accommodations.

Academic Integrity

Academic honesty is required in all work you submit to be graded. You may not submit work done with (or by) someone else. You may not examine or use work done by others to complete your own work. You may discuss assignment specifications and requirements with others in the class to be sure you understand the problem. In addition, you are allowed to work with others to help learn the course material. However, with the exception of the student mentors and your partner on group assignments, you may not work with others on your assignments.

All code you submit must be your own with the following permissible exceptions: code distributed in class, code found in the course text book, and code worked on with an partner. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.

"It is the opinion of the faculty that for an intentional first offense, failure in the course normally is appropriate. Suspension for a semester or deprivation of the degree in that year may also be appropriate when warranted by the seriousness of the offense." - Student Handbook (2009-2010, pg18 Section I.B.3.b.i)

Please see me if there are any questions about what is permissible.

External Links

• C++ compiler errors wiki
• GDB Howto
• Companion web site for textbook
• C++ Language Tutorial
• wxWidgets

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:42 PM