CS50x2-002 Fall 2015 Syllabus

From A-State Computer Science Wiki
Jump to: navigation, search

CS5012/5022/5032 Accelerated Structured Programming/Accelerated Object-Oriented Programming/Accelerated Data Structures

Section 001 Spring 2015

Instructor

Dr. Jason L Causey
OfficeABI 206Office Hours10:45-11:15 TR; Zoom and in-person meetings at other times are available by appointment.
Phone870-972-3978 ext. 8182Emailjcausey@astate.edu

Materials

Textbooks

Starting Out with C++, 8th ed. (ISBN: 9780133769395), by Gaddis, Tony. Pearson

Data Structures and Algorithms in C++, 4th ed. (ISBN: 9781133608424), by Adam Drozdek. Cengage Learning

Software

A programmer's text editor (such as Komodo Edit or Atom), a Secure Shell client (such as PuTTY) (available for free download online.)

General Statement

Computer Science undergraduate core for graduate students needing enhanced programming background. Covers programming techniques, data structures, and algorithms.

Goals and Outcomes

After completing this course, you will be familiar with structured and object-oriented programming paradigms in the C++ language, and have an understanding of several fundamental data structures. You will be able to classify and perform basic analysis of algorithms. You will have built the base of knowledge necessary to succeed in our graduate program.

Student Learning Outcomes

Course-Level Outcomes

After completion of this course, students will have met the following student learning outcomes:

  • Demonstrate a general understanding of computing technology.
  • Design and implement programs in the C++ programming language.
  • Ability to use an industry-standard toolchain for writing, compiling, and executing C++ code.
  • Demonstrate an understanding of the basic principles of computer programming.
  • Demonstrate an understanding of the Structured Programming paradigm.
  • Develop algorithms and programs to apply mathematical concepts.
  • Apply critical thinking and problem-solving skills to develop solutions to non-trivial programming problems.
  • Demonstrate technical communication skills through written algorithms and code documentation.
  • Understanding Abstract Data Types: motivations and basic concepts.
  • Understanding of the behavior of basic data structures (lists, stacks, queues, trees (binary trees and tree traversals), graphs).
  • Ability to analyze a problem and determine the appropriate data structure for the problem.
  • Understand the importance of data modeling and data structures in advanced programming.
  • Understand and analyze elementary algorithms: sorting and searching.
  • Ability to analyze the impact of data structures technique on the performance of algorithms (time and space complexity)/programs.
  • Data structure implementation issues. Understanding of dynamic versus array implementations of data structures, factors involved in deciding on an implementation technique.
  • Practice in writing modular programs using the data structures that have been studied.
  • Understanding the mechanics of code design, organization, and the development environment.
  • Understanding data structure implementation in C++ using header files and implementation files.
  • Demonstrate adeptness of object oriented programming in developing solutions to problems demonstrating usage of data abstraction, encapsulation, and inheritance
  • Be familiar with basic techniques of algorithm analysis
  • Be familiar with writing recursive methods
  • Be familiar with advanced data structures such as balanced search trees, hash tables, priority queues and the disjoint set union/find data structure
  • Be familiar with several advanced sorting algorithms including quicksort, mergesort and heapsort
  • Be familiar with some graph algorithms such as shortest path and minimum spanning tree
  • Master analyzing problems and writing program solutions to problems using the above techniques

Degree-Level Outcomes

CS 5012/5022/5032 is intended to provide core undergraduate Computer Science competencies linked to the following B.S. degree-level student learning outcomes:

  • Graduates of the B.S./B.A. Computer Science degree program attain the ability to apply knowledge of computing and mathematics appropriate to the discipline.
  • Graduates of the B.S./B.A. Computer Science degree program attain the ability to analyze a problem, and identify and define the computing requirements appropriate to its solution.
  • Graduates of the B.S./B.A. Computer Science degree program attain the ability to design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs.
  • Graduates of the B.S./B.A. Computer Science degree program attain an understanding of professional, ethical, legal, security and social issues and responsibilities.
  • Graduates of the B.S./B.A. Computer Science degree program attain the ability to analyze the local and global impact of computing on individuals, organizations, and society.
  • Graduates of the B.S./B.A. Computer Science degree program attain recognition of the need for and an ability to engage in continuing professional development.
  • Graduates of the B.S./B.A. Computer Science degree program attain the ability to use current techniques, skills, and tools necessary for computing practice.

Scheduled Topics

  • C++: types, operators, variables, program structure/syntax, Selection and repetition
  • Functions (pass-by-value and pass-by reference), Recursion: Writing recursive functions. Direct and indirect recursion
  • Complexity analysis (to be worked in throughout), Arrays and Pointers,
  • Files, Sorting, searching (BubbleSort)
  • Structures: Abstract data types and their usage, Structures VS. parallel arrays, the Random Access File
  • Dynamic Memory, Exception Handling, Classes and Objects
  • Composition of Objects, Operator Overloading, Singly-linked list, doubly-linked list
  • Queues, circular lists, stacks, and the Class Template
  • Inheritance, Virtual Functions and Polymorphism
  • Sparse Tables, Skip Lists, Self-Organizing Lists, Priority Queues
  • Binary trees, Balancing Trees, Self-Adjusting Trees
  • Heaps, B-Trees, Tries
  • Graphs (paths, cycles, spanning trees), Eulerian and Hamiltonian Graphs, Graph Coloring, NP-Complete problems
  • Decision Trees, Efficient Sorting Algorithms, Hashing, Data Compression

Course Website

Homework, resources, and current scores for the course will be posted at http://cscade.cs.astate.edu. I will explain the login procedure. Additional course information, including a course schedule, is available at http://wiki.cs.astate.edu/index.php/CS50x2_Fall_2015.

Attendance Policy

Attendance will be taken each day. Since all our activities build on previous lectures (just like a math class), attendance is crucial. If you must miss a class, it is your responsibility to cover the material that was covered in class on that day. Check the course website and contact the course instructor if you must miss a class.

Grades

Homework will be assigned regularly to reinforce the lecture material. The homework due dates will be posted with the assignment. Assignments will be graded according to the criteria posted at http://wiki.cs.astate.edu/index.php/CS50x2_Grading_Guidelines_(Causey). Late homework will receive reduced credit as shown below. We will also have short weekly exams (quizzes).

Grade Breakdown Grading Scale Late Homework Penalty
Exams/Quizzes 33% 70 - 100 P 1st day late -10%
Homework 50% < 70 F 2nd day late -30%
Final Exam 17% 3rd day late -50%
4 or more days late -100%

Classroom Courtesy

Please be respectful of others and keep in mind that this is a learning environment. Discussion is encouraged, but please try to remain on-topic. Always be on time for class — excessive tardiness will count as absence; tardiness on an exam day may result in reduced credit. Although you are encouraged to discuss problems and assignments with each other, cheating (including, but not limited to, plagiarism) is unacceptable and will not be tolerated. If you are caught cheating, you will receive a zero score (minus an additional penalty on programming assignments as shown in the Grading Scale) for that assignment and the Department and/or University may choose to take further action (See the Academic Misconduct Policy in the A-State Student Handbook (pg. 17) and Plagiarism in a Programming Context). Turn off or silence all phones and other noisy electronic devices (including watches and music players) during class. All electronic equipment is prohibited during exams (with the exception of calculators for some exams if announced), and all caps or hats which cover the eyes must be removed or turned backward. Students who become disruptive to the class will be asked to leave.

Important Dates

Midterm Grades
Oct 14 (W)
Last Day to Drop a Class
Nov 18 (W)
Final Exam
Dec 14 (M) @ 10:15a

Additional Information

  1. REDIRECT User:Jcausey/AAS Statement

Official grades must be obtained from the Student Self-Service website, or in person during my office hours. Neither the department secretaries nor I can discuss grades over the phone. You can track your progress in this course from the "Gradebook" section of the [Mimir] web application.

Any other questions should be directed to me through email or during my office hours. This is a general policy statement and is subject to change; this page will be updated as needed with the most current policies. More policies and information are available on the course website (see above). All A-State policies also apply to this course, as listed in the Student Handbook. Please read and be familiar with the information there as well.