Posts tagged "algorithms" « SaltyCrane Blog

Free Computer Science courses online

Date: 2009-06-30 | Modified: 2009-07-08 | Tags: algorithms, preferences | 2 Comments

I found out there is a video lecture series to go along with my new book The Algorithm Design Manual. The audio level is really low, but I think it will complement my book reading nicely. There are also lecture notes and homework assignments. It also turns out MIT has a huge collection of free courses online. Not all of them have video though. I listed some interesting Computer Science related courses with video below. After more searching, I found UC Berkeley also has a number of free courses online, including four Computer Science courses with video. The final source ...

Find the N longest lines in a file with Python

Date: 2009-06-28 | Tags: algorithms, python | 4 Comments

Here's a Python problem I attempted recently:

Write a program to read a multiple line text file and write the N longest lines to a new file. Where N and the file to be read are specified on the command line. Optimization is important.

Here's my solution:

import sys

def main(filename=sys.argv[1], 
         N=int(sys.argv[2])):
    """ Finds the N longest lines in filename and writes to filename + ".new"
    """
    lines = open(filename).readlines()
    lines.sort(cmp=lambda x,y: cmp(len(y), len(x)))
    open(filename+".new", "w").write("".join(lines[:N]))

if __name__ == '__main__ ...

How to reverse words in a sentence using Python and C

Date: 2009-04-22 | Tags: algorithms, c_cplusplus, python | 2 Comments

This is a technical problem I attempted recently. The problem was to reverse the words in a sentence. For example, The quick brown fox jumped over the lazy dog. becomes dog. lazy the over jumped fox brown quick The. I had to solve the problem first using Python, and then using C. In addition, the C version could only use 1 extra character of memory. I solved the Python version easily, but the C version was too difficult for me. Here are possible solutions.

Python version

sentence = "The quick brown fox jumped over the lazy dog."
words = sentence.split()
sentence_rev ...

Python recursion example to navigate tree data

Date: 2008-08-19 | Modified: 2009-03-25 | Tags: algorithms, python | 8 Comments

Here is a simple Python example using recursion to navigate a nested Python data structure. Each node in the data structure contains 0 or more children. In this simple example, I look at each node and print the "text" indented according to the nesting level within the data structure.

Update 2008-09-15: Nihiliad posted an improvement to my example in the comments. It is much simpler. I have updated my example below.

Nihiliad's (improved) method

data = {'count': 2,
        'text': '1',
        'kids': [{'count': 3,
                  'text': '1.1',
                  'kids': [{'count': 1,
                            'text': '1.1.1',
                            'kids': [{'count':0,
                                      'text': '1.1.1 ...

SaltyCrane Blog