Natalie’s CSC 300 Archived Resources

Below are a bunch of resources that I think are helpful for CSC 300 students. If you have any questions come to an SI session or leave a comment below. You can also upload any of your helpful resources in the comment section!

My Session Schedule, Winter 2016

[box] Monday 12:00-1:00pm, DePaul Center C105

Wednesday 5:00-6:00pm, DePaul Center C105

Office Hour – Tuesday 12:00-1:00pm, DePaul Center C105[/box]

Can’t attend any of my sessions? Check out other CSC 300 SI leaders’ schedules here.

Final Review Problem Set II & KEY

Here are the links to the problem set and key. Good luck on the final exam and feel free to email me any questions!

https://docs.google.com/document/d/1aYh–qBSte3gF0_Ow2IWCLQpIdArk8LMxeIsVSyZ2eE/edit?usp=sharing

https://drive.google.com/file/d/0B_KjYvtHToCScGJYMm1vSmRIa0U/view?usp=sharing

Final Review Problem Set I & KEY

Download (DOCX, Unknown)

NOTE: The answer to the question about what does find(3) return is WRONGGGGGG! The correct answer is 1, but I accidentally messed up and couldn’t edit the pdf and didn’t have access to a scanner to rescan the document. 😛

Download (PDF, Unknown)

Midterm Review Problem Set II KEY

These are the solutions to the mock exam I gave out in my session yesterday. Good luck today!

Download (PDF, Unknown)

Midterm Review Problem Set I KEY & Problem Set II

Here’s the solutions to the mock exam I posted yesterday as well as the second mock exam that I handed out in my session today.

Download (PDF, Unknown)

Download (PDF, Unknown)

Midterm Review Problem Set I

Here’s the mock exam I made for the review session today. Solutions will be posted by the end of the day.

Download (PDF, Unknown)

HW 1 & HW 2 Solutions

Hi guys! Here are the .java files with my solutions to HW 1 & HW 2. Since HW 3 hasn’t been graded yet, I’m going to hold off on posting solutions for that. However, if you have any questions about HW 3, please shoot me an email.

It is very important that you understand the code that you write. If you had any problems with HW 1 or HW 2, please review my solutions and see if they help you understand what you could have done to solve the problems presented. If you are still confused or need some extra clarification, please don’t hesitate to contact me! 🙂

Also, just a note about my solutions… These are just MY interpretation of the solution. There are many, many ways these problems could have been solved. Some of you may have solutions that are much longer. Some of you may have more elegant, shorter solutions. In any case, if it works, it works. As long as you understand WHY it works, all should be good.

I tried to comment my code as best as possible, but if anything is still ambiguous feel free to ask. I’m a programmer not a writer after all… 😛

Download (ZIP, 4KB)

LinkedLists vs. Arrays

At some point during the past few lectures you may have asked yourself, “Hmm… why the would anyone ever want to use a LinkedList? Aren’t array’s good enough?”

There is one major advantage of using a LinkedList over an array: flexibility in size. As you should recall, when declaring an array, the size of the array must be set upon creation. If you declare you array to be of size 3, you’ll never be able to stick a 4th element into it. If you run out of space in your array, your only option is to create a brand new, larger array and copy the old data from the old array into the new one.

In comparison, LinkedLists are flexible in size. This is because as you add things to the LinkedList, you must simply create a new Node and connect it to your existing list. Think of it like having a tower of legos and adding an extra piece on the top (or bottom, or middle… wherever you like really).

Tldr: LinkedLists are expandable in size where as arrays are not.

Besides this difference, another major difference between arrays and LinkedLists is the way the data is stored in memory. Imagine memory space being represented as an empty room. Items stored in an array would adjacent in memory, like people standing shoulder to shoulder in a line (I’d put a picture here, but the stock photos are pretty terrible, so use your imagination!). If you stood facing the first person in the line of people and took one step down the line, you’d face the second person. If you took another step down the line you’d be facing the third person and so on. The correlation between you taking a step and facing the next person is kind of like indexing in an array.

Items in a LinkedList are stored much differently in memory. Using the same analogy, Nodes in a LinkedList would be like multiple people spread out about the room. Even though these people aren’t directly next to each other, they know where there neighbor is. If you stand facing the first person/node in this list and want to go to see the next person/node, all you have to do is ask first where his neighbor is and go where he points.

Tldr, items in arrays are adjacent in memory & items in LinkedLists are spread out (but still connected).

Nodes & LinkedLists

This past week we covered our first real data structure of the course: the LinkedList. For those of you still slightly confused about the function of LinkedLists and how they interact with Nodes, here’s my crash course explanation…

The Node class makes up the foundation of the LinkedList class. Think of a LinkedList as a list made up of many, separate items. Each item will be represented by a Node. The Nodes are like the lego blocks making up our LinkedList. Each Node only has to be aware of two things: (1) It’s data value and (2) It’s next neighbor. In other words, each Node knows what number it represents and who it’s connected to.

Since all of our Nodes are connected (via node.next variable), our LinkedList object only needs to know about the FIRST Node in the list. As such, the LinkedList’s only member variable is the Node variable first. One way to picture this is like holding a ribbon of carnival tickets. Since all of the tickets are connected, you only need to hold on to one end of the ticket ribbon. Even though you hold on to only one ticket you can still get to every other ticket; there’s no need to hold all of the individual tickets in your hands! Since each ticket is connect to it’s neighbor ticket and each ticket has a value, I think this is a good real world analogy for a LinkedList.

tickets

About Me…

Hi, everyone! I’m excited to be serving as your Supplemental Instruction (SI) leader for CSC 300 this quarter. I took CSC 300 in Winter Quarter of last year. I really enjoyed the CSC 300/301 sequence, and I’m hoping you all will too. This class has proven to be very useful as I’ve found that I’ve thoroughly applied my knowledge of data structures throughout many of my upper level CSC courses. Get used to coding in Java is also very useful as many subsequent courses in your curriculum will involve assignments in Java.

Since I’ll be spending a lot of time in CSC 300 and in sessions/office hours with you, I’d like to share a bit about myself. As I mentioned in class, I’m currently a Senior majoring in Computer Science with a minor in Math. I wasn’t always a CS major though. I actually switched majors from Chemistry at the end of my Sophomore year and last year I was SI leader for a General Chemistry course.

My hometown is Honolulu, Hawaii and my first time coming to the Midwest was when I started my first year at DePaul. Other than the extreme cold and high taxes, I love it here, and I still try to get out and explore the city as much as possible. I tend to keep myself busy between taking extra classes and my part-time job, but in my spare time I love doing photography, cooking, playing video games, and watching tv or movies. If there’s one thing I hate in this world, it would be mayonnaise. There’s not really a good reason for it, but just wanted to share.

Now that you know a bit about me, I look forward to getting to know all of you throughout the course of this quarter. I’m going to try my best to make my sessions not only informative, but fun as well.

Here are some resources from Fall 2015

11.17.2015 – Mock Exam Key

Here’s the key for BOTH of the mock exams I posted yesterday. Let me know if you have any questions or if anything is unclear!

Download (PDF, Unknown)

11.16.2015 – Final Exam Review

Hey everyone! As promised, here’s the mock exam we worked on in my session today as well as the extra exam. I couldn’t get to a scanner today, so I’ll post the keys to both of these documents tomorrow.

Download (PDF, Unknown)


Download (PDF, Unknown)

11.10.2015 – Stacks, Queues and Runtime Analysis

In my session last week, we took some time to identify the scenarios in which to use stacks and queues as well as how to choose whether or not to use a LinkedList or ArrayList for a couple of different situations. Stacks and Queues are two of the last major data structures we’ll be covering in this course. Make sure that you understand the uses of these structures as well as their “under the hood” implementations.

Here’s a zip with code from last week’s sessions. One file is a class that we wrote last week which contains a recursive solution to a problem as well as a non-recursive solution that utilizes a stack. The other file consists of a number of methods which you can use to practice determining run time.

Download (ZIP, 1KB)

11.02.2015 – Comparing Data Structures

Last week we were introduced to one more new data structure, the LinkedList. As we learn about run time analysis and the “cost” associated with certain operations, keep in mind how the differences in the implementation between arrays, ArrayLists and LinkedLists affect use. Here is a brief chart I wrote up pointing out some of the differences of these structures. I’m sure there will be more to add to this chart before the quarter ends, but hopefully this preliminary version still proves helpful.

Download (PDF, Unknown)

In my sessions last week we worked on identifying the unique attributes of the LinkedList data structure. We also practiced writing more recursive functions and writing methods that operate on LinkedLists so that we could see some of the actual syntax and java implementation of the structure. Here is a zip file with the code we worked on last week. As usual, please feel free to contact me with any questions about the code!

Download (ZIP, 1KB)

10.25.2015 – Varargs and More Recursion

This past week we reviewed portions of the midterm as well as covered some basic code examples with varargs and a challenge recursion problem. The code that we worked on in sessions this week is linked below.

Download (ZIP, 3KB)

If you still have questions about the midterm, please feel free to come to a session and ask about it, or shoot me an email!

10.13.2015 – Midterm Review Part II

This is the other mini quiz we covered in review today. I’ll upload a key later tonight but try your hand at this one for now!

Download (PDF, Unknown)

10.12.2015 – Midterm Review Part I

Here’s the mini quiz I created went over in my session today. As a reminder tomorrow I will be holding another review session from noon to 1pm with new problems and activities!

Download (PDF, Unknown)

10.07.2015 – Methods & the Memory Model

This past week, we focussed on how various methods are represented on the Java runtime stack. In particular, we worked through a couple of recursive examples to see how recursive calls get their own slots of memory in the runtime stack.

We also discussed the differences between primitive and reference data types. Here’s a summary chart below.

Download (PDF, 29KB)

Here is a zip file of the code we worked on in my sessions this week.

Download (ZIP, 5KB)

In this file you will find two recursively defined functions : Harmonic sums and the Fibonacci sequence. See if you can trace how these recursive calls are executed and stored on the runtime stack. You will also find a file called MemoryExamples that include a couple of simple, but non-sensical methods that you can use to practice illustrating what the memory model looks like after execution.

There are also two files in this zip that are related to creating and using reference classes. The Coffee class is a reference class representing a cup of coffee. It has a few basic methods as well as a .toString method so that the info in the Coffee object can be displayed in a human-readable format. The CoffeeShop class contains a main method where a few different Coffee objects are created. The interesting part of this is at the line “Coffee kevinCoffee = kimCoffee;” What happens here? Think about this as you run this program and see what the different created coffees look like.

10.03.2015 – Wrestling With Recursion

In my sessions this past week, we covered some basic recursion techniques and practiced implementing solutions to recursive problems. From experience, I can definitely say that recursion is one of the more tricky concepts to get hang of. Personally, I have found that practice and time are really necessary to master recursion, but check out the recursion tips below for more techniques.

Professor Rogers has been integrating the topic of recursion to the way the Java memory model works and how variables are stored on stack and heap. Next week, I will be doing more recursion examples tying in these memory concepts.

I’ve uploaded a zip file of the code we worked on in my sessions this week. Included are three recursive program classes (RecursiveFactorial, RecursivePower, and RecursivePrintArray). The iterative version of print array is included so you can see the contrast between the iterative and recursive implementation.

Week4_Code

Another great resource that a student mentioned to me is a site called thenewboston. There’s a bunch of Java tutorials here, so check it out!

09.23.2015 – All About ArrayLists And Arrays

This week, we started looking at our first data structures in Java! Yay! ArrayLists and Arrays are important (and useful) data structures to understand, and in my sessions this week, we wrote code that works with both.

Here’s the zip file with the programs from my sessions this week. There are two different program types. One finds the index of the minimum value in an Array/ArrayList and the other counts the number of odd and even numbers in an Array/ArrayList. Each program type has a file that works on Arrays and a file that works on ArrayLists. Check them out and see if you can identify the differences.

Download (ZIP, 5KB)

In my sessions this week we also worked on creating a chart detailing the differences between lists in Python and Arrays and ArrayLists in Java. This should help to distinguish what syntax to use when and the unique characteristics of each data structure.

Download (PDF, 28KB)

After looking at these resources, try these exercises  for more practice! Make them work for Arrays or ArrayList or both. Feel free to email me with questions you encounter while tackling these.

  1. Write a class that creates a user generated Array/ArrayList of integers and then uses another method to change all of the negative values in the Array/ArrayList to their positive counterpart (pretty much absolute value on the entire data structure).
  2. Write a class that creates a user generated Array/ArrayList of strings and then uses another method to count and return the number of strings in the Array/ArrayList that begins with the letter ‘a’. (HINT: Use the line “char first_char = string_var.charAt(0);” to get the first character of a string.)
  3. Write a class that creates a user generated Array/ArrayList of integers and then uses another method to reverse the order of the the numbers in the Array/ArrayList. Print out the original and reversed Array/ArrayList in main. (HINT: You can’t simply print out the data structure variable to see a human-understandable print out. You will need to go through and print the elements of the data structure one by one…hmmm, what does that sound like…? )

09.18.2015 – Java Basics

This past week, we’ve just started to cover some of the major differences between Python and Java. I hope that from the lectures in class, you’re starting to get a feel for Java syntax. In my past two sessions, we’ve worked on converting basic code from Python to Java and have pointed out how certain tasks differ between the two languages.

I’ve included a zip file with pairs of Python/Java code examples. Check them out and see if you can understand how one line in Python corresponds to one line (or many lines…) in Java.

Download (ZIP, 5KB)

Here’s also a chart of differences between Python and Java we’ve encountered so far (in terms of syntax).

Download (PDF, 26KB)

Tips

Runtime Analysis

Being able to look a program and determine its runtime is a very valuable and, dare I say, essential tool for any programmer. While many of you may have learned a very thorough and technical approach to determining O (big-O), here are some techniques I would suggest to get the gist of some code’s runtime without having to employ a ton of math.

  • Remember Murphy’s Law
    “Anything that can go wrong, will go wrong.”
    While not to be bringer of bad news, or an utter pessimist, I include this tip to remind you all the runtime analysis always accounts for the WORST CASE! When considering iterating over an ArrayList searching for some element, always express the runtime as if the element was the very, very last thing in the list. While best case is always a possibility, runtime analysis always expresses the time it would take if worst comes to worse. At least this way you’re never disappointed with the performance of your code!
  • Think in n
    When we express the runtime of some code in big-O notation, we always write “O(___)” where the blank is replaced by some expression in terms of n. What does n mean? n is an arbitrary value that represents the number of operations executed in the code when there are n elements in the input. For example, if you wanted to sum all of the odd numbers in an ArrayList of Integers and there were 5 Integers in the list, you’d have to check and potentially add 5 numbers. If there were 15 elements in the ArrayList, you’d have to do 15 operations. With n elements in the ArrayList, you do n operations. Thus, this method would have a runtime O(n). If it’s hard to think abstractly at first, think of some real number examples. Imagine if your input had 1 element, then 10 elements, and eventually abstract it so you can determine the runtime for n elements.
  • Seek Out Other Resources
    There are plenty of resources out there to help you to get a better understanding of runtime analysis. If you prefer the more mathy/technical explanation of runtime, seek out a discrete math explanation. There are a number of blogs, lecture notes, and web pages with explanations and examples galore. Here’s one page to help you get a basic idea of determining big-O with some nice examples.

Recursion Techniques

Recursion can be a tricky topic to understand, but try using some of these tips generated by myself and your fellow peers. If you have your own recursion technique that you’d like to share, please leave it in the comments on my page below!

  • Identify the Base Case
    When working on coding up a recursive method, it may be easiest to start by identifying the base case. To find the base case consider the following: How do you know when your method should stop recurring? What is the most simple version of the question that can be asked? The answer to these questions will help you identify your base case and give you a good starting block for your method.
  • Draw it Out
    From my personal experience working with recursion, I have found that keeping track of all of the recursive calls can be a real headache. To combat this problem I have found that drawing pictures of each call can help to understand the series of calls being made in your method before the base case is reached. Use arrows with labels above/below them to show what parameters are being passed into each call and what each call returns to its caller.
  • Start With Iteration
    If you are totally at a loss for how your recursive method should function, try coding the method using iteration first. Seeing how the method operates with loops can sometimes be useful in understanding how to it operates recursively.
  • Talk it Out
    Sometimes, the easiest way to approach a problem is not to think about it as a programmer, but to think of it as a person. Look at the problem and talk out what you (as a human being) would do to solve it. What steps would you take? What information do you need and how would you get it? By understanding the step-by-step process YOU would take, you can translate the logic of your procedure to code.
  • Don’t Give Up!
    Recursion is hard, but don’t give up! Keep in mind the benefits of understanding recursive programming, and don’t forget that there are many resources available to help you. In addition to Professor Rogers and myself, there are many other CDM options like the tutoring center on the second floor. Always remember, never give up!

Using and Utilizing Eclipse

Unlike in Python, coding in Java requires the use of an IDE, an Integrated Design Environment. For this class, Eclipse is the IDE we use. Getting to know some of the tips and tricks that Eclipse has to offer can make your coding life a lot easier, so I’ll try to post some of them I’ve come across throughout my coding career here!

  • Auto-complete Method Calls
    When coding in Eclipse, you may have noticed that Eclipse will try to auto-complete your method calls. When you start a method call on an object (ex: array. ) Eclipse will drop down a list of possible methods to call. Hovering over a method in that list will give a description of the method including what it does, the parameters it takes, and what it returns (if it returns something). This is a really helpful way to see what methods exist for a given object!
    Eclipse
  • ToDo’s
    Comments are very useful things in any programming language for keeping track of your ideas and making your code more readable to other programmers. There is a nifty comment you can use in your java file that results in Eclipse keeping note of that commented line. If you comment “//TODO” on a line, Eclipse will put a little clipboard next to that line on your side bar. This can be useful when you’re tackling a large project and want to keep track of which parts of a program you’ve completed and which parts you still need to address. When you delete the comment line, the memo goes away!
    TODO

General Tips for CSC 300

CSC 300 can definitely get challenging at times, but here’s some tips and tricks that helped me to ace the class when I took it.

  • Take notes!
    I’m a big proponent of note taking, especially if the topic is something you don’t understand well. During lecture, jot down any topics that were unclear or confusing and so that in the future you can ask myself or Professor Rogers to clarify.
  • Draw pictures as needed.
    Sometimes difficult concepts make a lot more sense when you draw diagrams or pictures!
  • Look at examples.
    Especially when trying to get a hang of the syntax of a new language, I find that looking at examples and understanding what lines of code correspond to what behavior of the program is very, very valuable.
  • Practice makes perfect!
    Cheesy, but true. Even if you do work in a group on a coding assignment, I would recommend you take time on your own to make sure you understand everything your group wrote. Start with a blank copy of the assignment and try to do it yourself. This will provide good practice in writing Java. It will also ensure you comprehend the material, or will expose which topics you don’t quite understand or need to brush up on.

 

Leave a Reply

Your email address will not be published. Required fields are marked *