Homework due and quiz #4 – Wednesday, March 2

Posted on February 24, 2016 by Kate Poirier

Section 3.3: #1, 2, 3, 4, 5, 26, 30, 32…with the following modifications:

  1. Hand in solutions for questions 1-5 (including the odd ones). Those questions ask for big-O estimates; instead give big-\Theta estimates for each. (This sounds like it’d be harder than giving a big-O estimate, but I think you’ll find it’s easier to think about big-\Theta.) Notice that questions 3 and 4 are asking you to ignore comparisons in the for and while loops…for your HW you can either ignore them or include them, just be clear about what you’re doing.
  2. For questions 26, 30, and 32, you’ll have to go back to your solutions from HW#1 and the practice problems from section 3.1. Include those algorithms in pseudocode on your HW#4 paper. (If you didn’t write down those algorithms correctly, here’s your chance to try again.)

Please staple your pages and write “HW#4” and your name at the top of the first page.

FYI, on Monday we’ll analyze the complexity of the binary search algorithm.

Posted in Homework, Quizzes | 2 Comments

Complexity of the linear search algorithm

Posted on February 24, 2016 by Kate Poirier

Benjamin asked a great question after class today. The linear search algorithm is:

procedure linear search(x: integer, a_1, a_2, \dots a_n: distinct integers
i := 1
while(i \leq n and x \neq a_i)
    i:=i+1
if i \leq n then location: i
else location:= 0
return location

We said that we were usually interested in the worst-case scenario, but the question applies no matter where x is on the list.

For each value of i (that means for each round in the while loop), there are two comparisons:

  1. Is i \leq n?
  2. Is x \neq a_i?

    3. If the answer to both of these is yes, you stay in the loop. From one perspective, that means there’s a third comparison:

  3. Are both answers above “yes?”

We hadn’t been including this third comparison in our calculation that, in the worst case, there are 2n+2 comparisons. If we had, the answer would have been 3n+2. It’s certainly not wrong to include the third comparison, but it’s not absolutely necessary either and 2n+2 is what I’d expect to see from you. What I told Benjamin is that, if he were to hand in his solution, as long as he described all the comparisons clearly and in full detail (especially the third one, since I wouldn’t be anticipating it…but actually all three since he won’t anticipate what I’m anticipating and what I’m not anticipating), then he’d get full credit.

In practice, this distinction doesn’t really matter. Both functions 2n+2 and 3n+2 are \Theta(n). (If all you’re looking for is the order, you can also safely be sloppy about the constants we discussed at the end of class.) Of course, in this class, you might be asked for the precise count of basic operations as well as the order, so be prepared to explain each step of your count explicitly.

 

Posted in Discussion | 2 Comments

Homework due and quiz #3 – Wednesday, February 24

Posted on February 17, 2016 by Kate Poirier

Section 3.2 #28, 30, 33, 34, 36, 37

Posted in Homework, Quizzes | Leave a comment

Quiz #1 – comments

Posted on February 16, 2016 by Kate Poirier

Here is one correct algorithm that locates the position of the largest even integer in a set of n integers:

procedure largest even location (a_1, a_2, . . . , a_n : integers)
k := 0
largest := -\infty
for i := 1 to n
 if (a_i is even and a_i \geq largest) then
  k := i
  largest := a_i
return k {the desired location (or 0 if there are no even integers)}

There are certainly many correct ways to achieve this result, but this one is nicely compact. One of the trickiest parts for many of you was that initial value for largest. Some of you started with the value a_1 there, but would run into problems with input lists where the first element is a large odd number. Some of you started with the value 0 there, but would run into problems with input lists where there are even integers, but they’re all negative. Starting with -\infty clears this hurdle.

Most people’s pseudocode was fairly readable, but I want to emphasize that starting with the name of the procedure and a description of the inputs is critical for communicating what you’re doing. Some people’s answers were more code than pseudocode, which tended to make them less readable. Pseudocode isn’t a language, so there aren’t precise rules, but a nice description is given in the Appendix of your text. Roughly, you should be able to give pseudocode to a human who doesn’t understand code, but who is very good at following directions, and have him or her be able to understand it. When in doubt, show it to someone.

When you’re writing these short, simple algorithms, you should always check your work using a short example input. Some of you would have caught your initial error immediately and others would have noticed that their algorithm wasn’t returning any answer. Again, when in doubt, show your work to someone.

Posted in Quizzes | Leave a comment

Reminders/update

Posted on February 10, 2016 by Kate Poirier

Monday, February 15 is Presidents’ Day, so our next meeting is Wednesday, February 17. You’ll complete Quiz #2 (based on homework #2) then.

Feel free to post discussion questions on the OpenLab at any time. Don’t forget to add the “Discussion” category to your post; the Discussion page will display these posts.

I’ve updated the Links page to include the online graphing calculator I used in class today, along with an article about algorithms without coding.

Posted in Uncategorized | Leave a comment

Homework due and quiz #2 – Wednesday, February 17

Posted on February 10, 2016 by Kate Poirier

Section 3.2 #2, 8, 10, 16, and the following:

(1) Assume that n < 2^n whenever n is a positive integer. Use this to show that \log(n) is O(n).

(2) Show that n! is O(n^n).

(3) Determine whether f(x)=x^2 is O(x) or is not O(x).

(4) One algorithm for solving a problem uses n log(n) steps. Another algorithm for solving the same problem uses n^{\frac{3}{2}}. Which algorithm would be better for a large number of inputs n?

Keep in mind that by “\log(n)” here, we mean the logarithm with base 2.

For hints, consult examples 1-9 in section 3.2.

Posted in Homework, Quizzes | 2 Comments

Introducing Carlos Paredes

Posted on February 8, 2016 by Cparedes95

Your major ? 

My major is computer science

How did you get interested in math/computer science ? 

I’ve always been interested in computer programming, after high school I decided that’s what I wanted to do. Since I enjoyed doing math Aswell, It made my decision easier.

What do you hope to do after you graduate city tech? 

After I graduate city tech I hope to get a good job with my degree and start a business of my own.

What topics interested you most from MAT 2440? 

Doing proofs because I never understood it…

What you hope to get out of this course?

I hope to get a really good grade, but I really hope to get a better understanding in structures and algorithm.

Other hobbies or interest? 

I enjoy learning, challenging myself , making ideas into reality, playing baseball and basketball and sleeping

Posted in Introduce yourself | Leave a comment

Introducing Stephen Sokolovsky

Posted on February 7, 2016 by Stephen S

My major is Computer Science. I chose this major because I was introduced to programming during my freshman year in high school and I found it interesting. After graduating, I hope to get a career in this field and be successful. I look forward to learning more about algorithms and computer science in this class.

Posted in Uncategorized | Leave a comment

Introducing Mohamed Basse

Posted on February 7, 2016 by Mohamed Basse
  • Your major

My major is Computer Science

  • How you got interested in math/computer science

I watched too many hacker/tech movies and the rest is history.

  • What you hope to do after you graduate from CityTech; short-term goals, long-term goals, whatever…

Get a job  in the tech space or begin a startup specializing in simplifying creative arts software. Then maybe direct of couple of indie-films that only show at film festivals and eventually end on Netflix.

  • What topics interested you most from MAT 2440

Algorithms really. trying to learn how to create my own and open up new possibilities in simplification of tasks other than attendance taking haha

  • What you hope to get out of this course (I don’t mean which grade you want!

A better understanding of discrete math.

  • Other interests/hobbies you have

I watch ALOT of movies. I take photos in my spare time.  I also enjoy long walks through the city and am on a constant journey of self-discovery.

Posted in Introduce yourself | Leave a comment

Introducing Benjamin Lin

Posted on February 7, 2016 by Benjamin Lin
  • Your major- computer science
  • How you got interested in math/computer science-Magic….To be honest I just somehow end up here.
  • What you hope to do after you graduate from CityTech; short-term goals, long-term goals, whatever… -I am still lost in the process .-. I may never find the way out.
  • What topics interested you most from MAT 2440.- Coding.
  • What you hope to get out of this course (I don’t mean which grade you want!) To be honest….. I just want a A on my grade, other than that .-. a less stressful class.
  • Other interests/hobbies you have. Playing games all day.
    Games playing atm: Blade & soul- Lv 45 Force Master- Master Hong sever
  • Dislike(I just feel like adding this in)- writing long essay. >:(
    …. or a long paragraph.
Posted in Introduce yourself | 1 Comment