Introduction to Computer Science Skip to Main Content Home Syllabus Lectures Assignments Exams Staff Rutgers Home SAS CS Introduction to Computer Science Computer Science Department Home Syllabus Lectures Assignments Exams Staff Lectures Week Topics Learning Objectives Resources Week 1 Logistics Algorithm design, development and analysis using Pseudocode Algorithmic thinking (1.1) Given a problem specification, determine the inputs, outputs and error conditions of the algorithmic solution to the problem. (1.2) Develop algorithms involving sequential control (1.3) Develop algorithms involving selection control: IF, IF-THEN-ELSE (1.4) Write algorithms that include decision statements using Boolean expressions with relational and logical operators (1.5) Develop an appropriate algorithm to solve a problem or accomplish a task involving sequential and selection control. (1.6) Count the number of operations executed in an algorithm involving decision statements. Logistics slides Lecture slides Pseudocode reference sheet Week 2 ALGORITHM DESIGN, DEVELOPMENT, and analysis USING PSEUDOCODE Algorithmic thinking and analysis (2.1) Given a problem specification, determine the inputs, outputs and error conditions of the algorithmic solution to the problem (2.2) Analyze algorithms by counting operations executed in the algorithm (2.3) Develop algorithms involving iteration using a WHILE loop (2.4) Count the number of operations executed in an algorithm that involves iteration Lecture slides Pseudocode reference sheet Week 3 Program Design, Development, and Analysis: Programming in Java Algorithm Implementation, basic Java (3.1) Java Programs (3.1a) Edit, compile, and run a program (3.1b) Find and correct errors in a program (3.2) Built In Data Types (3.2a) Identify the four primitive types in Java and operations on those primitive types. (3.2b) Declare and assign values to variables. (3.2c) Use Java identifier conventions (camel-case). (3.2d) Evaluate results of assignment statements involving arithmetic operations. (3.2e) Write and evaluate statements involving compound assignment operators (+=, -=, etc.). (3.2f) Evaluate given expressions that involve the primitive types and/or Strings and operations performed on them. (3.3) Input And Output (3.3a) Use System.out.println(…) method to output information as a String in a Java program. (3.3b) Use command-line arguments for input to a Java program. (3.3c) Convert the command-line String arguments to ints using parseInt method. (3.4) Booleans And Logical Operators (3.4a) Evaluate and construct complex Boolean expressions using the logical operators (&&, ||, !). (3.4b) Construct truth tables to evaluate complex Boolean expressions. (3.4c) Compare and contrast equivalent Boolean expressions. (3.5) The Math Class (3.5a) Use the following constants and methods in Java Math class to write solutions to problems. Constants:PI Methods: abs, ceil, floor, max, min, pow, random, round, sqrt (3.6) Casting (3.6a) Evaluate expressions involving implicit type conversions. (3.6b) Identify cases where explicit casting is needed. (3.6c) Determine the results of executing program segments involving implicit type conversions and/or explicit casting. (3.6d) Write solutions to problems involving explicit casts. (3.6e) Identify program errors due to incorrect type assignments. (3.7) Relational Operators (3.7a) Evaluate and write expressions using the relational operators (<, >, =, <=, >=, !=). (3.7b) Explain the dangers in comparing double values with == or !=. (3.7c) Write, compile and execute programs in Java. (3.7d) Find and correct errors in a program. (3.7e) Determine the most appropriate data type for a particular specification. (3.7f) Determine the solution to Boolean expressions. Textbook reading 1.1, 1.2 Lecture slides Book video Java reference sheet Tools installation guide Week 4 Program Design, Development, and Analysis: Conditionals and Loops Algorithm implementation, conditionals and loops (4.1) Conditionals And Loops involving if, if-else, while, for, do-while (4.1a) Write program code to satisfy program specifications using expressions, conditional statements, and iterative statements. (4.1b) Determine how many times a program segment will execute. (4.1c) Determine if two or more code segments result with the same outcomes. (4.1d) Describe the behavior of code segments involving control structures. (4.1e) Describe why a given code segment does not work as intended. (4.1f) Determine the most appropriate selection/control control structures for a particular specification. (4.1g) Implement and trace code involving compound assignment idioms within loops (i++). (4.1h) Implement and trace code involving break and continue (4.1i) Recognize conditions that would result in an infinite loop scenario. (4.1j) Describe the process and result of nesting control structures. (4.1k) Trace program segments involving nested control structures. (4.1l) Write program code involving nested control structures. (4.1m) Create appropriate test cases for if statements and test if statements in a comprehensive manner. (4.1n) Identify the scope of variables within a program involving loops and conditionals. (4.1o) Count the number of operations executed in program or program segment. (4.11) Use debugging tools to step through code in order to identify errors at various stages of program development. Textbook reading 1.3 Lecture slides Book video Java reference sheet Week 5 Program Design, Development, and Analysis: Arrays The array data structure (5.1) Arrays in Java (5.1a) Declare, create, and initialize one-dimensional(1D) and two-dimensional (2D) arrays. (5.1b) Explain Java’s default array initialization. (5.1c) Describe and implement initializer lists to initialize arrays. (5.1d) Describe and illustrate memory representation and allocation involving array implementations in Java. (5.1e) Distinguish between valid and invalid array index references in code segments. (5.1f) Identify ArrayIndexOutOfBoundsExceptions in program code segments. (5.1g) Implement Java code to manipulate 1D arrays including, but not limited to, the following tasks: Traverse and display the elements in an array in order and in reverse order. Reverse the elements in an array. Find and report the minimum/maximum value in an array. Find and report the index of the minimum/maximum value in an array. Find the average of numerical values in an array. Exchange values of two elements in an array. Shift elements in array to the right/left as specifications describe. Count the number of elements in an array satisfying given specifications. Remove elements that satisfy certain conditions from an array. Remove duplicate values from an array. (5.1h) Demonstrate the use of the enhanced for loop (for-each) when writing code involving arrays. (5.1i) Distinguish between situations that can and that cannot utilize an enhanced for loop. (5.1j) Determine the result of program code that traverses and manipulates the elements in a 2D array. (5.1k) Trace and implement code to traverse and manipulate 2D arrays in row-major and column-major order. Textbook reading 1.4 Lecture slides Book video Week 6 Program Design, Development, and Analysis: Input and Output Input and Output in Java (6.1) Utilize different types of input and output In a Java program (6.1a) Use command line arguments to provide input values to programs. (6.1b) Explain the meaning and functioning of String args[] as a parameter to main. (6.1c) Explain the need for Integer.parseInt() and Double.parseDouble when using command line input. (6.1d) Use standard output in programs: System.out.print(), System.out println() (6.1e) Use the following methods of StdIn in programs to read individual tokens from standard input: isEmpty(), readInt(), readDouble(), readBoolean(), readString() (6.1f) Use the following methods of StdIn in programs for reading characters from standard input: hasNextChar(), readChar() (6.1g) Use the following methods of StdIn in programs for reading lines from standard input: hasNextLine(), readLine(), readAll() (6.1h) Use the following methods of StdIn in programs for reading from standard input to arrays: readAllInts(), readAllDoubles(), readAllBooleans(), readAllStrings(), readAllLines() (6.1i) Explain and implement an end-of-file sequence to end user input. (6.1j) Redirect standard output to a file when executing a program. (6.k) Redirect from a file to standard input when executing a program. (6.1l) Demonstrate piping the output of one program to the input of another Textbook reading 1.5 Lecture slides Book video Input Output Library Week 7 Program Design and Development: Functions and Modules Writing functions (7.1) Functions and Modules (7.1a) Explain the meaning and use of static methods in Java. (7.1b) Use pre-existing functions/modules when writing program code. (7.1c) Define and use static methods with and without parameters in program code. (7.1d) Define and use static methods with and without return values in program code. (7.1e) Define and use static methods that include arrays as parameters or return types. (7.1f) Explain and illustrate the call stack for a program that includes multiple method calls. (7.1g) Trace and write programs that include methods having multiple return statements. (7.1h) Write program code that includes calls to Java Library methods. (7.1i) Describe the meaning of each part of a method signature. (7.1j) Identify the scope of variables in a program that includes multiple methods. (7.1k) Explain the difference between local variables and parameter variables. (7.1l) Explain the difference between a method implementation and a method call. (7.1m) Trace and write programs involving overloaded methods. (7.1n) Identify the scope of a variables in a program with multiple methods and method calls. (7.1o) Use debugging tools to step through code in order to identify errors at various stages of program development. Textbook reading 2.1, 2.2 Lecture slides Book video Week 8 Program Design, Development, and Analysis: Recursion Recursive algorithms (8.1) Recursion (8.1a) Determine the purpose or output of a recursive method by tracing the program code. (8.1b) Compare the readability and efficiency of iterative and recursive solutions to the same problem. (8.1c) Identify the base case and general case for a recursive solution. (8.1d) Design and implement a recursive method to solve a problem. (8.1e) Explain and illustrate the call stack developed in a recursive solution to a problem. (8.1f) Check and test a recursive method for correctness. (8.1g) Use debugging tools to step through code in order to identify errors at various stages of program development. Textbook reading 2.3 Lecture slides Book video Week 9 SPRING BREAK – No Lecture – No Recitation Week 10 Program Design, Development, and Analysis: Object Oriented Programming OOP - Using Data Types (9.1) Object Oriented Programming (OOP)-Using Data Types (9.1a) Explain the meaning of data type. (9.1b) Distinguish between object and reference. (9.1c) Distinguish between primitive data types and object references. (9.1d) Declare String reference variables and create String objects in a program. (9.1e) Write code that manipulates/processes Strings by calling String methods. (9.1f) Explain the immutability of Strings. (9.1g) Explain the results of concatenating Strings with primitive data types using the + operator. (9.1h) Given a class API, write a client program that creates objects of that class and call methods defined for that class and illustrate the call stack and memory allocation for the execution of this client program. (9.1i) Use the concepts of Object Oriented Programming (classes, objects, and methods) to write a program that solves a problem. Textbook reading 3.1 Lecture slides Book video Week 11 Program Design, Development, and Analysis: Object Oriented Programming OOP - Creating data types (10.1) Object Oriented Programming (OOP)-Creating Data Types (10.1a) Identify appropriate behaviors and attributes of real-world entities to create a class. (10.1b) Write program code to define a new data type by creating a class. (10.1c) Design and implement a simple class from given specifications. (10.1d) Explain the purpose of a constructor. (10.1e) Explain the purpose of overloading constructors. (10.1f) Distinguish among parameter variables, local variables, and instance variables. (10.1g) Differentiate between public and private access modifiers. (10.1h) Explain the purpose of declaring variables with the final modifier in a class. (10.1i) Explain the difference between instance methods and class methods. (10.1j) Write instance methods that have new data type objects as parameters. (10.1k) Write instance methods that have new data type objects as return types. (10.1l) Write instance methods that have new data type objects as local variables. (10.1m) Write a client program that will create and use objects of a class that you wrote. (10.1n) Write client programs that test all methods of your newly created data type. (10.1o) Document all instance methods by including pre- and post- conditions in your code. Textbook reading 3.2 Lecture slides Book video Week 12 Program Analysis: Performance (Big-O) Algorithm complexity analysis (11.1) Performance (11.1a) Explain algorithmic efficiency as it relates to speed and space consumption. (11.1b) Recognize typical orders of complexity (O(1), O(log n), O(n), O(n log n), O(n^2), O(n^3), O(2^n)) (11.1c) Identify the basic operations in an algorithm and determine the running time of an algorithm by counting its basic operations. (11.1d) Express the running time of an algorithm as a function of the input size and derive the complexity class of the algorithm. (11.1e) Categorize algorithms according to their Big O complexity. (11.1f) Describe space and time efficiency tradeoffs when designing algorithms. (11.1g) Identify the best case, worst case, and average case Big O complexities of algorithms. (11.1h) Compare the efficiencies of different algorithms that perform the same task. (11.2) ArrayList (11.2a) 1. Represent collections of related object reference data using ArrayLists. (11.2b) Implement Java code to manipulate ArrayLists including, but not limited to, the following tasks: Traverse and display the elements in an ArrayList Traverse using a for or while loop Traverse using an enhanced for loop Insert, delete, and modify objects in an ArrayList. (11.2c) Explain the differences between the array and the ArrayList data structures. (11.2.d) Compare the run time analysis for algorithms implementing arrays and algorithms implementing ArrayLists. (11.2.e) Choose the appropriate data structure (arrays/ArrayLists) for use in a given application. (11.2f) Compare the advantages and disadvantages of using Arrays and using ArrayLists in a Java program. Textbook reading 4.1 Lecture slides Book video Week 13 Program Design, Development, and Analysis: Sorting and Searching Sorting and searching (12.1) Searching (12.1a) Given an array /ArrayList of values, write a linear (sequential) search method to locate a specified value in the array. If the value is not present in the array, indicate that. (12.1b) Given an ordered array/ArrayList of values, write a non-recursive binary search method to locate a specified value in the array/ArrayList. If the value is not present in the array/ArrayList, indicate that. (12.1c) Count the number of comparisons made when a given search algorithm is executed and the search key and the array/ArrayList of values are provided. (12.1d) Identify all elements in a given array/ArrayList that are examined when a given search algorithm is executed and the search key and the array of values are provided. (12.1e) Determine the best case, and worst case Big-O analysis when a given search algorithm is executed and the search key and the array/ArrayList of values are provided. (12.2) Sorting (12.2a) Given an array of values, give a step-by-step illustration of executing the selection sort on the array. State the array contents after each pass of the sort. (12.2b) Given an array of values, give a step-by-step illustration of executing the insertion sort on the array. State the array contents after each pass of the sort. (12.2c) Determine the best case and worst case Big-O analysis of the selection sort. (12.2d) Determine the best case and worst case Big-O analysis of the insertion sort. (12.2e) Write a program that sorts an array of numerical values using the selection/insertion sort (12.2f) Write a program that sorts an array/ArrayList of objects using the selection/insertion sort. (12.2g) Compute statement execution counts and informal run-time comparison of sorting algorithms. Textbook reading 4.2 Lecture slides Book video Week 14 Program Design, Development, and Analysis: MERGESORT AND ANALYSIS Recursive algorithm analysis (14.1) Recursive Binary Search (14.1a) Given an ordered array of values, write a recursive binary search method to locate a specified value in the array. If the value is not present in the array, indicate that. Identify the base case and the general case in the algorithm. (14.1b) Count the number of comparisons made when a recursive binary search algorithm is executed and the search key and the array of values are provided. (14.1c) Identify all elements in a given array that are examined by a recursive binary search algorithm when the search key and the array of values are provided. (14.1d) Determine the best case and worst case Big-O analysis for a recursive binary search algorithm when the search key and the array of values are provided. (14.2) Mergesort and Analysis (14.2a) Given an array of values, give a step-by-step illustration of executing the mergesort on the array. State the array contents after each pass of the sort. (14.2b) Determine the best case and worst case Big-O analysis of the mergesort. Textbook reading 4.2 Lecture slides Book video Week 15 Extra class time for exam giveback and review Connect with Rutgers Rutgers Home Rutgers Today myRutgers Academic Calendar Calendar of Events SAS Events Explore SAS Departments & Degree-Granting Programs Other Instructional Programs Majors & Minors Research Programs, Centers, & Institutes International Programs Division of Life Sciences Explore CS We are Hiring! Research News Events Resources Search CS Home Back to Top Copyright 2020, Rutgers, The State University of New Jersey. All rights reserved. Rutgers is an equal access/equal opportunity institution. Individuals with disabilities are encouraged to direct suggestions, comments, or complaints concerning any accessibility issues with Rutgers web sites to: accessibility@rutgers.edu or complete the Report Accessibility Barrier or Provide Feedback Form.
