Skip to Main Content

Introduction to Computer Science

Computer Science Department

Lectures

Week
Topics
Learning Objectives
Resources

Week 1

Logistics
Algorithm design,  development and analysis using Pseudocode
  • (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.

Week 2

ALGORITHM DESIGN, DEVELOPMENT, and analysis USING PSEUDOCODE
  • (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

Week 3

Program Design, Development, and Analysis: Programming in Java
  • (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.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.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.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.

Week 4

Program Design, Development, and Analysis: 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.

Week 5

Program Design, Development, and Analysis: Arrays
  • (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.

Week 6

Program Design, Development, and Analysis: Input and Output
  • (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

Week 7

Program Design and Development: Functions and Modules
  • (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.

Week 8

Program Design, Development, and Analysis: Recursion
  • (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.

Weeks 9/10

Program Design, Development, and Analysis: Object Oriented Programming
  • (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.

Week 11

Program Design, Development, and Analysis: Object Oriented Programming
  •  
  • (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.

Week 12

Program Analysis: Performance (Big-O)
  • (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.

Week 13

Thanksgiving Break

Have fun and relax!

Rutgers holds Monday, Thursday, Friday classes
NO CS111 classes

Week 14

Program Design, Development, and Analysis: 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.

Week 15

Program Design, Development, and Analysis: MERGESORT AND 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.