CS588 - Data Structures, Algorithms and Software Design

Tuesday/Thursday 12:00am-12:15pm, Streibel Hall Room 115

An introduction to programming in C++, spanning major topics such as classes, templates, data structures and computer algorithms; with a particular emphasis on efficient software development for scientific computing.

News


Course announcements are posted here:

Contact Information


Email and Phone:

tdesell@cs.und.edu
701-777-3477
Email is the best and most reliable way to contact me.

Office Hours:

Streibel Hall 220
To be decided and by appointment.

Address

Department of Computer Science
University of North Dakota
Streibel Hall Room 220
3950 Campus Road Stop 9015
Grand Forks, North Dakota 52802-9015
Date Topic Lecture Notes/Lab Files Reading
01/13/2015 Course Information
01/15/2015 Intro to C++ (program structure, variables, constants, operators, basic I/O) cs588-01-intro.pdf cpluspus.com tutorial - Basics of c++
01/20/2015 Variables, Functions and Parameter Passing cs588-02-variables_parameter_passing.pdf
01/22/2015 Lab 1 2015_lab1.cxx
01/27/2015 File Input/Output (I/O) cs588-03-file_io.pdf
01/29/2015 Lab 2
02/03/2015 Vectors and Strings cs588-04a-vectors.pdf
cs588-04b-strings.pdf
02/05/2015 Lab 3 parse_string.cxx
02/10/2015 Travel
Lab 4
02/12/2015 Travel
Lab 4
02/17/2015 Travel
Lab 5
02/19/2015 Travel
Lab 5
02/24/2015 Arrays cs588-05-arrays.pdf
02/26/2015 Lab 6
03/03/2015 Pointers cs588-06-pointers.pdf
03/05/2015 Lab 7
03/10/2015 Sorting, Basic Algorithm Analysis, Growth of Functions (Asympototic Notation), Recurrences cs588-07-sorting_growth_of_functions.pdf
03/12/2015 Lab 8
03/17/2015 No Class - Spring Break
03/19/2015 No Class - Spring Break
03/24/2015 C++ Classes - Part 1 cs588-08-classes.pdf
stack.cxx
stack.hxx
03/26/2015 Lab 9
03/31/2015 C++ Classes - Part 2
04/02/2015 Lab 10
04/07/2015 No Class - Travel
04/09/2015 No Class - Travel
04/14/2015 C++ Templates, Trees cs588-09-templates.pdf
04/16/2015 Lab 11
04/21/2015 Namespaces & Exceptions, Heaps cs588-10-namespaces_exceptions.pdf
04/23/2015 Lab 12
04/28/2015 Type Casting, Graphs cs588-11-typecasting.pdf
04/30/2015 Lab 13
05/05/2015 Dijkstra's Algorithm
05/07/2015 Lab 14

Course Description


An introduction to programming in C++, spanning major topics such as classes, templates, data structures and computer algorithms; with a particular emphasis on efficient software development for scientific computing.


Objectives


At the completion of this course, students should be proficient in the C++ programming language and have a foundational understanding of data structures and algorithms in computer science. Main objectives include:

  • Introduce sorting and searching algorithms.
  • Introduce recursion.
  • Introduce fundamentals of the C++ language -- STL, Classes and Templates.
  • Introduce different data structures such as lists, trees and graphs.
  • Introduce fundamentals of algorithmic analysis (big "Oh" notation).

Outcomes


Students will gain knowledge/understanding of the following:

  • Algorithmic analysis.
  • Sorting algorithms.
  • Data structures -- lists, trees, graphs.
  • Programming paradigms -- recursion, divide-and-conquer, greedy algoriths, dynamic programming.
  • The C++ standard template library (STL).
  • C++ program semantics: classes and templates.
  • C++ memory management.
Students will aquire the ability to do the following:
  • Create and debug programs in the C++ programming langauge.
  • Analyze an algorithm to determine its runtime.
  • Implement fundamental data structures.
  • Understand and properly use the availble datastructures and algorithms in the standard template library (STL).


Pre-Requisites


None.


Text


Algorithms Unlocked, by Thomas H. Cormen


Grading


The grade will be determined as follows:

  • 70% - Labs/Homeworks
  • 15% - Test 1
  • 15% - Test 2

There will be the following grade distribution:

  • [90 - 100]: A
  • [80 - 89.9999...]: B
  • [70 - 79.9999...]: C
  • [65 - 69.9999...]: D

Any grading problems, appeals or questions can be brought before the instructor for discussion.


Academic Integrity


The development of the individual problem solving skills needed for computer programming is one of the major objectives of this course. Students are to work independently of each other in completing the programming assignments. Any exception to this rule will require documentation signed by me allowing the collaborative work.

If you need help, you are welcome to consult with your instructor, your teaching assistant, or the staff of the department's Instructional Help Desk in 109A Streibel Hall. A submission of source code that you did not develop or homework assignments that was not your individual writing will be treated as plagiarism. These assignments will receive zero points and you may be referred to the Associate Dean of Student Life as a case of Scholastic Dishonesty.


Attendance


Class attendance and lab attendance are required. Any student missing more than 6 classes without a doctors excuse will fail the course. The classroom is the primary venue for course material, announcements, and other information relevant to the course. An on-line course management system may be used to make some information available to students, but this is intended to enhance, not replace, classroom interaction.


Homework and Lab Submission


Code for homeworks and labs must be commented and properly formatted (see different coding styles, I prefer 1TBS) or points will be taken away. The final homework submission must be submitted through Moodle. Each homework will list its grading criteria.

Late assignments will have their grades penalized by 15% the first day, and 30% the second day. No assignments will be accepted more than two days late. Homeworks are to be done individually (see Academic Integrity) and may involve a significant amount of programming, so start them early.


Lab Policies


All lab assignments must be completed by the end of the lab session. Any exception will require proper excuse with permission granted before the end of the lab session. Partial credit may be given to incomplete work.

Any issues related to the machines in the computer labs can be sent to cslabs@cs.und.edu.


Students with Disabilities


Upon request, the Computer Science Department will provide reasonable accommodations for students with disabilities as specified in the policies of the UND office of Disability Services for Students (DSS). You must contact your instructor to request and arrange accommodations.