M E M O R Y L E S S N E S S

- background - assignment and notes - license - download -

-[ background ]-
 
In the Spring of 2003, I took a course in stochastic processes. The second exam was take home and it required some coding, which I did in TurboPascal, as in the case of my tic tac toe program one year later (the posting of which reminded me of the code from my stochastic processes class).

-[ assignment and notes ]-
 

A local store uses an (s, S) inventory policy for a particular product. Every Friday evening after the store closes, the inventory level is checked. If the stock level for the product is greater than s, no action is taken. Otherwise, if the stock on hand is less than or equal to s, an amount S-s is procured over the weekend and is available when the store re-opens on Monday morning.

Let {X_n, n = 1, 2, …} be the stock on hand when the inventory is checked on Friday evening of week n and let {Z_n, n = 1, 2, …} be the demand for product during week n.

Then for any ω ∈ Ω,

	Xn+1(ω) = Xn(ω) - Zn+1(ω)	if s < Xn(ω), Zn+1(ω) ≤ Xn(ω)
	Xn+1(ω) = S - Zn+1(ω)	if Xn(ω) ≤ Zn(ω) ≤ S
	Xn+1(ω) = 0	otherwise.

Let s = 3, S = 5, X₀ = 0 and assume customers arrive at the store according to a Poisson process with rate λ = 4 per week. (Each customer wants one unit of product.)

Phase I of the exam required the proof that {X_n, n = 1, 2, …} is a Markov chain and writing its transition matrix. These are intuitive (or you’re looking for the answers to your exam, assuming the prof. still uses this exam), so I won’t include them here.

Phases II and III of the exam required some coding.

Phase II

A) Write a program to generate (i.e., fill in) the one-step transition matrix for a passed value of S. Print the one-step matrices for S = 4.

B) Let π^[0] = (1, 0, …, 0). Write a program to compute the equilibrium probabilities of the Markov chain using Jacobi iteration.
Also, plot π_j^[0] as a function of n, i.e., the number of Jacobi iterations.

…

Jacobi Iteration.

Jacobi Iteration is a simple computational technique for obtaining the equilibrium probabilities of a Markov chain using a series of matrix multiplies rather than solving a system of linear equations.

Let π^[n] be the probability row vector representing the probability of occupying a given state after n transitions. That is, π_j^[n] = P{in state j after n transitions}.

By conditioning on the state occupied at transition n we have

π^[n+1] = π^[n] P  (Eqn 1)

where P is the one-step transition matrix for the Markov chain. In the limit as n goes to ∞, π^[n] goes to π, the vector of equilibrium probabilities. Depending on the system and the desired accuracy, convergence can be quite rapid.

To compute the equilibrium probabilities, start with π^[0], then compute π^[1], then π^[2] and so on using Equation 1 until π^[n+1] is “close” to π^[n]. For this problem, stop iterating when

Max{|π_j^[n+1] - π_j^[n]|, all j in State Space} = 0.0001.

Computational note: Due to round-off error by the computer, it may be necessary to “re-normalize” π^[n] every few iterations so that its elements sum to one. To do this, add up the first m-1 elements of the vector π^[n] (assuming the chain has m states) then set the m^th element equal to one minus the sum. The elements now sum to one.

The source code and binaries for the solutions to these Phase II questions are linked below. I’m not including Phase III’s code because, unlike Phase II’s, it does not have many possible uses outside the context of this exam. Phase II’s code is relevant because somewhere, someone might want to write a simple program to perform Jacobi iterations or to write one-step transition matrices. This code could easily be extended for other (non-Poisson) arrival distributions and/or for generation of the n-step transition matrix.

-[ license ]-
 
The code and the accompanying binaries are distributed with NO LICENSE; don’t blame me if this messes up your computer. Please do let me know if you find an error, though.

-[ downloads ]-
 

• Phase II, Part A - [ source ] | [ binary ] | [ source + binary (.zip) ]
• Phase II, Part B - [ source ] | [ binary ] | [ source + binary (.zip) ]

- background - actual assignment - algorithm - notes - license - download -

-[ background ]-
 
fj and I had a chat this morning about the end of civilization (he sent me that wiki link, which precipitated the discussion). Anyway, that links to technological singularity (or vice versa, I forget). This discussion reminded me that for a class I took during the Spring of 2004, I had to write a program that plays tic tac toe. Technically, I should say “we,” since I had a partner, but I wrote the program and he did the manual enumeration of a tic tac toe decision tree. I think I picked the easier half of the assignment. If you want to see the tree, too bad. You’ll have to do that part of the assignment yourself.

The class was “Cognitive Engineering;” it was all about Turing machines and Turing tests such. This assignment related to the cognitive aspects of problem solving and whether or not a machine could duplicate them. It’s a very (extremely) simple AI. So noone can ever say that I didn’t do my part to help bring about a technological singularity. Maybe that’s not such a good thing.

-[ actual assignment ]-
 
From the no longer online course website:

PART A

Draw the state transition tree for playing tic-tac-toe. This diagram should outline all of the possible states of the game; starting with a blank diagram and moving to all possible ends. Note that who goes first (X or O) doesn’t really matter because when we get done, we can just replace all X’s with O’s and O’s with X’s to get the other tree. Because your program (see below) will have X go first, do this tree. Also, when making your tree realize that many different configurations are the same. For instance, there are only 3 possible initial moves (middle, side or corner) even though there are 9 spaces. If you can rotate the game to get an identical configuration, these are the same in terms of strategy (i.e. if you are playing tic-tac-toe, nobody cares if you rotate the paper before making your move).

PART B

Design and construct a computer program to play tic-tac-toe. Assume that ‘X’ always goes first, and that your opponent can be either ‘X’ or ‘O’. You way use any computer language you wish, within reason.

Material turned in for this assignment should include: an enumeration of the problem space; a written verbal description of your computer algorithm, and a disk containing your program.

-[ algorithm ]-
 
From the document we turned in:

This tic tac toe program was written in Turbo Pascal for Windows version 1.5. The algorithm that the program uses to play tic tac toe is rather simple. First, the program allows the user to choose if s/he wants to be play as X or O. If the user chooses O (and thus chooses to allow the computer to play first), the computer’s first move is to randomly select one of the corners. If the user chooses X (and thus, chooses to go first him/herself), the program chooses a space based on the user’s choice. If the user has selected a corner, the program chooses the middle. Otherwise, the program chooses a corner at random. After the first turn, the program is designed to play strategically.
The strategy employed by the program is used until a winner is determined. The program is designed to first try to win. It examines all of the squares, and if it is capable of winning (having three X’s or O’s in a row, depending on whether it is X or O), it does so. If it cannot win, it again examines all nine squares and attempts to block the user from winning. If the user has two in a row and can win on the next turn, the program will block the user. If the program cannot win or block, it will attempt to play offensively. If either pair of side squares is free (e.g. above and below the middle or to the left and right of the middle), it will randomly pick one of these free sides. If no pair of side squares is free, it will try to take the middle square. If the middle square has already been taken, it will randomly choose a free corner. If no corner is free, it will randomly choose a free side.
The program allows the user to play multiple times without exiting. Additionally, it keeps track of how many times it has won, how many times the user has won, and how many tie (or cat) games there have been. For more detail about how the program works, please see the source code.

-[ notes ]-
 
This written in Turbo Pascal, for that ultra-retro feel (actually, because that was the only compiler I had at the time), but the executable file should work on most Win32 installations. All ASCII art included is believed to be in the public domain. If you use the code for anything, please let me know by leaving a comment. Thanks.

This needs work, but it can beat me. Of course, I always sucked at tic tac toe. According to the professor, there’s a flaw in the logic that allows the user to always win. I’ve been unable to find it, though. Please let me know if you find it.

We got a 100 on this project, despite the “flaw,” in case you’re wondering. I still got a B in the damn class, though.

-[ license ]-
 
The code and the accompanying binary are distributed with NO LICENSE; don’t blame me if this messes up your computer. Please do let me know if you find an error, though.

-[ download ]-
 
[ source ] | [ binary ] | [ source + binary (.zip) ]

lots of stuff has gone down since i last wrote…i’m about to tell you all about it.

but first, who invited this guy?

what was with that hair? and the smirk? man, i was a little punk. that picture is from 1994. check this one out:

in 1997, i entered college. and, thankfully, i had already done something about the hair. apparently, i was less of a smirker, too.

that being said, here’s a summary of what’s happened to me: i’ve graduated, i’ve gotten married, i’ve spent a week in vegas, and i still haven’t found a job. if you’d like more details, click the “read more” link. if not, you won’t offend me if you skip them.

where to begin? hrm…

on may 15, i graduated from texas tech with an MS degree. i didn’t walk, though, so the actual time of the graduation was pretty uneventful. we slept in that day, and then liz and i went to see Mean Girls. very funny film. after that, i went to my friend j3ph’s mom’s graduation party (she’d gotten her PhD in music that morning) and hung out with him and his brother and some other people for a little bit. we played frisbee; it was neat. i then went home and had a quick dinner with liz before going out with friends as a sort of “party” to celebrate the graduation. yeah. check out photos from said event right here (sure, there’s only one picture there now. there’ll be more, as soon as i scan them). we met up with seth, tara, and joel at the library (not the place they keep the books OR the old dance club here in l-town, but an all right bar in the depot district), and had a few drinks. noel and trevor and their respective lady-friends joined us after a bit, as did fastmikey. the bouncer was giving noel’s girlfriend stephanie shit about being underage, so they left shortly for klusoz. eventually, we all joined them there. i don’t remember too many details about what all happened at klusoz, except that 1) thriftstore cowboys were playing, 2) i drank a lot of beer, 3) i bumped into a table and spilled the drinks of everyone sitting there, and 4) i bought 6 shots of jim beam for me, liz, seth, tara, noel, and stephanie. a good time was had by all. after klusoz, the six of us who had shots went to seth’s parents’ house and drank some more, i think. we sat around and talked for a while, then noel gave liz and i a ride home.

the next morning (5/16), liz and i woke up and i went to taco bell to get our post-drunk breakfast. after that, we went to seth’s parents’ house again for brunch, and saw seth’s parents, sister, brother-in-law, and niece and nephew. that was pretty fun, aww yeah.

the next few days weren’t very interesting, really; just hanging out and going to work and stuff.

but that thursday (5/20), liz and i drove to san angelo to see the burden brothers. this was completely insane, especially since we were already planning to see them the next night in lubbock at a weird festival-thing with a bunch of other bands. every once in a while, though, you’ve just got to give the universe the finger and remind yourself that you aren’t really as old as you usually feel. anyway, we napped that afternoon, ate dinner, and then drove to san angelo (about a 3 hour drive). we got there around 10:30, so we missed the opening bands and the first few burden bros. songs. it was weird; when we’ve seen them in lubbock, it’s usually been pretty packed. when we saw them in amarillo, it was really packed. there were under 20 people there in san angelo. the show was good, though. afterward, we met the band (again), and they signed the picture that we’d taken at that amarillo show. we told the drummer, taz, that we’d come from lubbock and that we were looking forward to the show the next day. he told us that he’d give us passes, but we’d already bought tickets. he got us backstage passes instead, which was pretty cool. aww yeah. anyway, after the show and stuff, we drove back home, arriving here at about 3:30am. we had to be at work at 6am that day, so we didn’t bother sleeping, just came home and showered and did a little packing for our trip to las vegas. we did stop by krispy kreme on the way to work, though, since we were up early enough to get donuts before work. work was long and slow that day; i was like a zombie. after work, we ate lunch and then napped for about 2 hours. after that, we went to the “x-fest” thing at the west texas canyon amphitheater. it was pretty cool, i guess. lots of bands. i was too tired to appreciate it fully, i think, but i did have a good time. we found the burden brothers’ manager and he gave us our backstage passes. we watched the first few bands (i forget who all played), and were up front for the bros’ set. it was cool. i caught a drumstick, aww yeah. after that, we met up with them where they were signing autographs, then went backstage and hung out for a bit. we decided, though, that we’d like to sit down, so we went back to the main amphitheater and watched the other bands. drowning pool was pretty cool; better than i expected. we also saw damageplan; also pretty cool, but not as cool as pantera. we actually left during their set, due to the tired-ness. also, we didn’t want to stick around for the last band, saliva, since we had no desire to see them. just like last year. yeah. anyway, we went home and ate dinner, and all was well as we went to bed, not too late that night, but pretty late considering the lack of sleep. yes.

saturday (5/22), we got up at 9ish, finished packing, and went to the mall so liz could by the shoes she wanted. from there, we went to the airport, where we caught our plane to las vegas. yet again, we didn’t get to sit next to each other on the plane; alas. anyway, when we got to vegas, we were stuck in the terminal for a few minutes because of a “security situation” (i never did figure out exactly what was up), but then we were on our way. we stopped by the tropicana, where i’d reserved a tuxedo. i tried it on, and, well, it rocked balls. then we went to the treasure island to check in for our wedding the next day. we thought, “hell, we can walk there, it’s not that far.” no, it’s really not. however, when unsure of exactly which direction it is, and when carrying one’s luggage + rented tuxedo, i highly DO NOT recommend walking from the tropicana to the treasure island. anyway, it all worked out. after treasure island, we checked in at the time share where my aunt was generous enough to have gotten us a room. we hung out for a while, then went back to the treasure island to catch the limo that took us to the court house to get our marriage license. $55 + legal IDs is all you need; it’s open 24 hours on weekends. after we paid the fee and signed the forms, we were heading back to the limo and this guy (who was waiting in line with a female companion) said to me, “hey man, do they like check IDs and shit?” “uhh, yeah.” yes, mr. guy, these marriages are legal. that was pretty funny. then it was back to treasure island, then back to our hotel, then sleep.

the next day (sun. 5/23) we got married at the treasure island wedding chapel. here’s some photos (3, as of right now - more coming when i scan them) taken at the actual event. after the ceremony, we ate lunch and then walked across the street to the venetian, where we rode in a gondola (photo also in this album). that night, we went to some hawaiian restaurant (the name of which i forget) and had a good time. ‘twas a good wedding day; i had lots of fun.

the next week (mon. 5/24 - fri. 5/28) was spent in las vegas, seeing the sights. we took lots of pictures, some of which might be scanned someday. highlights of the week: star trek: the experience on monday; gambled at the mgm grand, went to the m&ms and coca-cola stores, went up in the eiffel tower at the paris hotel on tuesday; saw the white tigers (and other cats, as well as the dolphins) at the mirage on wednesday; went to hoover dam and the shark reef (at mandalay bay) on thursday; and went to see The Day After Tomorrow on friday. we walked a lot, including walking through many of the other hotels and casinos, as well. it was an awesome honeymoon. sat. 5/29, we checked out of the timeshare, went to the airport, and waited for our plane. in the airport, we ran into jeff j., a guy i went to high school with, so i chatted with him a little bit before we got on the plane. liz and i actually got to sit next to each other that time, so that was cool. once we got home, we took a nap, and hung around the apartment.

since the vegas trip, not very much of note has really happened. just working and looking for a job. we went to lunch with oscar and colin the week after we got back; that was fun. last weekend (fri. 6/4, to be exact), we went to see nosmo king play at jake’s. good show, good show. we’ve watched a lot of movies, too. Shrek 2 is really cool. today, we saw The Stepford Wives. an updated version of the original (which we saw a few weeks back), i think, but the remake played up the dark comedy aspects more than the original. also, thankfully, it was more fast-paced.

this week, (wed. 6/9, to be exact), i drove to austin for a job interview. i also drove back from austin after the interview. that was a long day. lots of really hard rain, both on the way there and on the way back. i wish i would have brought a camera so i could take pictures of all of the weird signs one sees between here and there. my favorite was an apartment complex (i think…not sure exactly what it was) with a big sign that said “lobo village.” anyway, i left our apartment a little before 6:30am and got back here right at 12:30am. long day. but it’ll be worth it if i get an offer. i think the interview went well. we’ll see. i’m supposed to hear within a week.

hey there. i’ve wanted to write in this thing for a few days, but the chach house has been offline. yeah. so here goes.

so, for the third time, i’m announcing that i’m done with school. well, it’s only the second time i’m announcing that, really. the first was when i got my bachelor’s degree two years ago. it’s the third time i’ve thought that i was finished with classes for my master’s degree. (last summer and last fall, i thought i was done. pretty sure it’s true this time.) yup, no more school. at least at the mighty texas tech university. and definitely not in my department. i think seven years of one department is more than enough. i know other people who have been in school for 7 years (post-high school), but most of them have either changed departments or schools. even lil ou-skar, who’s also in grad school at tech in the same department as he got his undergrad degree in, took a semester (or a year?) off. this shows how lame i am, i suppose.

it’s weird to be done with school. not sure what to do next, since i don’t have a job. i mean, i’ve got a part time job that should help for a while (though i’ll likely have to quit soon), but i’d like to have more than that. at least a full time job. yeah. i’m not sure what to do now that i’m finished. there’s always been a “next step” before. when i finished high school, college was the next step. when i finished college (and didn’t find a job), getting a master’s degree was the next step. now that i’ve finished the master’s degree, there’s no next step. sure, i could get a PhD next. but i’m not going to. maybe someday, but i need some time off from school first. 20 years of school is enough for now. we’ll see about the future, though. of course, not staying on for another degree means that my TA paychecks will cease as well. which means that i really do need a job. more than just sappy talk about next steps. i need some cashflow.

also speaking of jobs, there’s a job fair tomorrow at the civic center. i suppose i’ll be going.

in other news, liz and i are getting married. soon. in las vegas. this very month. this totally rocks and i’m really excited. aww yeah. we went to the mall today, and i bought converse all stars (chuck taylor), because i have to represent during the wedding. heh. they’ll look classy with a tuxedo, i think. i also bought some slightly (very, so far) more comfortable converse shoes because the skechers i bought in august are falling apart (actually, just the right one is). so, the next time i see bruno/steven, he won’t accuse me of betraying my roots, because i’ll still be wearing converse.

so, that’s about it. graduating this weekend. not walking. getting married later this month. all is well, except for the lack of a job.

last week, i had my comprehensive final exam for my master’s degree. boy, was it fun! actually, no, it kind of sucked. but i passed. check it out:

now, all i have to do is pass my classes. shouldn’t be too much of a problem, i think.

oh yeah, and there’s the whole having to find a job thing, too.

yesterday, i had an interview in amarillo. it went okay, i think. now, i have to submit written answers to some questions that they e-mailed me. i guess the job would be all right. it is amarillo, though. not too different from lubbock, but that may or may not be a good thing.

i saw j3ph and erin when i was there. they’re doing well; they bought a house. j3ph is probably my oldest friend. not “oldest” as in he’s old, but “oldest” as in i’ve known him longest. i listed him as a reference for the job i was interviewing for, and i had to say how long i’ve known him. 22 years. that’s a long time, given that i’m 25.

anyway, i ate dinner with them and then drove back to l-town. ‘twas a long day, but i think it was good.

maybe i’ll start posting in this more often again, IF YOU COMMENT-SPAM FUCKERS WILL LEAVE IT ALONE. maybe not.